AT_wtf19_c2 题解

· · 题解

题意

二维平面上有 n 个黑点 (x_i,y_i)，其余点为白点。每次操作可任选两个整数 x,y，将 (x,y),(x,y+1),(x+1,y) 三个点的颜色取反。要求最后只剩一个黑点，求该黑点坐标，保证有解。1\le n\le 10^4,-10^{17}\le x_i,y_i\le 10^{17}。

题解

先考虑值域较小的情况。尝试将点转化到同一条线上，取 Y \le \min y_i 并选择 y=Y 这条横线。观察转化过程，发现点 (x_i,y_i) 会贡献到所有满足 {y_i-Y\choose t} 为奇数的点 (x_i+t,Y)。根据 Lucas 定理的结论，该限制等价于二进制下 t\subseteq (y_i-Y)。

若将答案 (x_0,y_0) 贡献到直线 y=Y 上，最靠边的贡献点分别满足 t=0 和 t=y_0-Y，即横坐标分别为 x_0,x_0+y_0-Y。于是将初始点暴力贡献到该横线上，再找到最靠边的黑点横坐标 L,R，答案即为 (L,R-L+Y)。时间复杂度 \mathcal O(nV)。

以上做法告诉我们，找到 y=Y 上最靠边的黑点横坐标 L,R 即可求出答案。由于所求 L,R 分别对应 t=0 和 t=y_0-Y，只需求出任意一个黑点横坐标 X，即可从高位到低位倍增求出 L,R。

具体地，对每个二进制位 2^k，若 (X-2^k,Y) 仍为黑点，则 y_0-Y 和当前 t 该位均为 1，需要更新 X\leftarrow X-2^k，最终得到的值即为 L。对 R 的求解是类似的，只需变减为加即可。判断某个点的颜色可以枚举所有初始点计算贡献，单次复杂度 \mathcal O(n)，总复杂度 \mathcal O(n\log V)。

于是目标变为找到横线上任意一个黑点。考虑对所有点按 (x-y)\bmod 3 划分等价类，每次操作三个等价类内各取反一个点，三者的黑点数奇偶性均改变。又因为最终状态只有一个黑点，每个状态下都存在黑点数为奇数的等价类。

在该横线上同样划分等价类，找到奇数个黑点的等价类 c，再对其不断二分，每次向奇数个黑点的一侧递归，即可找到一个黑点。

二分中需求解的问题为：给定 l,r,c，求初始点贡献到横线上后，[l,r] 区间内横坐标模 3 为 c 的黑点个数奇偶性。由于不关心具体个数，可对每个初始点分别求出贡献点数奇偶性。由于贡献点异或只会导致点数减少 2，这些奇偶性异或起来即为最终黑点数奇偶性。

于是分别对初始点 (x_i,y_i) 求 [l,r] 内有多少模 3 为 c 的 X 满足 (X-x_i)\subseteq (y_i-Y)。对 t=X-x_i 考虑，设 f_{k,liml,limr,c} 表示填了 2^k 及更高位，这些位上满足包含限制，是否仍然等于上下边界，当前值模 3 为 c 的数字个数奇偶性，直接数位 DP 即可，单次复杂度 \mathcal O(\log V)。

令 V=10^{17}，由于坐标绝对值不超过 V，可取 Y=-V。此时贡献点在 [-V,3V] 内，答案 x_0,y_0 满足 x_0\ge -V,x_0+y_0\le 2V，可推出 y_0\le 3V。若贡献到竖线 x=-V 同样可得 x_0\le 3V,y_0\ge-V，于是答案坐标在 [-V,3V] 之间，倍增和数位 DP 从 2^{58} 开始即可。

关于复杂度，瓶颈在于二分找任意黑点的 \mathcal O(n\log^2 V)，倍增求 L,R 的 \mathcal O(n\log V) 不在瓶颈上。提交记录。