NOI 一轮复习：根号平衡

2. 值域根号分治

2.2 例题

[ICPC 2025 Shanghai R] Round screws

首先考虑修改时怎么考虑，假设原来相邻的三个数是 $a,k,b$ ，将 $k$ 改成 $t$ ，则 $(a\operatorname{xor} t)+(t\operatorname{xor} b)\ge (a\operatorname{xor} t)\operatorname{xor}(t\operatorname{xor} b)=a\operatorname{xor}b$ ，构造一个使等号成立的 $t$ 只需要不让加法进位，即在 $a,b$ 两二进制位都为 $1$ 时为 $1$ ，都为 $0$ 时为 $0$ ，否则无关。

这样发现一次修改等价于删除。设 $f_i$ 代表以 $a_i$ 结尾的最小代价，则：

$f_i=\min_{k=0}^{i-1}\{f_k+C(i-k-1)+(a_i\operatorname{xor}a_k)\}$

令 $g_k=f_k-Ck$ ，等价于：

$f_i-Ci+C=\min_{k=0}^{i-1}\{g_k+(a_i\operatorname{xor}a_k)\}$

相当于维护一个数据结构，支持插入 $(g,a)$ ，查询时给定 $t$ 求 $g+(a\operatorname{xor} t)$ 的最小值。如果我们直接暴力做的话我们记录给定的 $a$ 时 $g$ 的最小值，那么插入是 $O(1)$ 而查询是 $O(V)$ 的，看到这个值域范围不难想到围绕值域去做一些根号平衡。

让插入时多枚举一些信息，比如查询的数的一部分。这里枚举查询的数的二进制后 $9$ 位。也就是说，我们维护 $h_{H,L}$ 表示查询的数的二进制后 $9$ 位为 $H$ ，插入的信息的二进制前 $9$ 位为 $L$ ，这样在插入时就可以直接统计后 $9$ 位的贡献（因为这部分查询的数已知），查询的时候只需要维护前 $9$ 位的贡献即可。代码。