本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-22 09:55:09

题意

二维平面上有 $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)$ 不在瓶颈上。提交记录。