vjudge
给定 \(n\) 个数对 \((x_i, y_i)\)，现在要构造一个长度为 \(m\) 的序列 \(d_1 \sim d_m\)，要求 \(m \le 40\)，对于每个 \(i\) 满足以下条件：构造 \(m - 1\) 个数对 \((a_j, b_j)\)，对于每个 \(1 \le j \le m\)，满足以下四种情况之一（其中 \((a_m, b_m) = (x_i, y_i), (a_0, b_0) = 0\)）：
- \(a_j = a_{j - 1}, b_j = b_{j - 1} + d_j\)
- \(a_j = a_{j - 1}, b_j = b_{j - 1} - d_j\)
- \(a_j = a_{j - 1} + d_j, b_j = b_{j - 1}\)
- \(a_j = a_{j - 1} - d_j, b_j = b_{j -1}\)
无解输出 \(-1\)，有解输出 \(d\)，以及每个 \((x_i, y_i)\) 的每个 \(j\) 是哪种情况。
\(n \le 10^5, |x_i|, |y_i| \le 10^9\)。
先判掉一些显然无解的情况。比如所有 \(x_i + y_i\) 的奇偶性必须相同，都和 \(\sum d_i\) 的奇偶性一致，因为即使暂时 \(a_j > x_i\)，后面还要回来，一去一回，奇偶性不变。
找不到其他无解的情况，不妨先来构造一下，因为 \(x, y\) 放在一起考虑太麻烦，而走一步能到达的点都是曼哈顿距离为 \(d\) 的，不妨转化为切比雪夫距离。具体的，将 \((x_i, y_i)\) 变为 \((x_i + y_i, x_i - y_i)\)，则条件转化为了 \(|a_j - a_{j - 1}| = d, |b_j - b_{j - 1}| = d\) 了，可以单独考虑。 单独解出来后计算方案就较为简单了。
其实问题就是转化为：为每个 \(d_j\) 分配一个符号，然后让它们的和为 \(x_i\)。（*）
这个还是比较经典的，我们令 \(d = \{1, 2, 4, \dots, 2^{30}\}(2^{31} > x + y)\)，最开始所有的数符号均为负号，假设集合 \(S\) 中的元素为正号，那么 \(-\sum d_j + 2\sum\limits_{u \in S} u = x_i\)，那么 \(\sum\limits_{u \in S} = \frac{x_i + \sum d_j}{2} = \frac{x_i + 2^{31} - 1}{2}\)。那么 \(S\) 为这个值中二进制为 \(1\) 的位即可。
但注意，这个只能在 \(x_i\) 为奇数的时候做，偶数就行不通了（解释了为啥最开始的 \(x_i + y_i\) 的奇偶性一定要相同）。偶数多加一个 \(1\)，强制其符号为负数即可（使 \(\sum d\) + 1）。
时间复杂度：\(O(n \log V)\)，\(m = 31 / 32\)
非常牛逼的构造题，用切比雪夫的思想将两部分分开，分别求解，求解时调整法即可。