CF1511G

CF1151G

简化题意：给定 \(n\) 个数 \(a_1 \sim a_n\)，以及 \(m\) 和 \(q\) 组询问。每组询问给定 l, r，对于哪些满足 \(l \le a_i \le r\) 的 \(i\)，求 \(a_i - l\) 的异或和。

\(l, r, a_i \le m \le 2 \times 10^5, n, q \le 2 \times 10^5\)。

算法一

有一个及其 naive 的想法是莫队 + 01 trie 维（反向建 trie），移动左端点想到与将树上的所有数 \(+1/-1\)，不断交换左右儿子即可。时间复杂度：\(O(q \sqrt m \log m)\)，应该过不了。

算法二

另一个比较粗暴的方式是逐位考虑，确定每一位的值。假设现在考虑第 \(j\) 位，那么 \(a_i - l\) 第 \(j\) 位为 \(1\) 当且仅当

\[2^{j} \le (a_i - l) \! \mod 2^{j + 1} < 2^{j + 1} \]

那么可以得到 \(a_i \mod 2^{j + 1}\) 的范围，结合 \(l \le a_ i\le r\)，二维数点做到 \(O(q \log^2 m)\)

算法三

根据题解，说倍增也是一个逐位考虑的过程，所以使用倍增解决这个问题。听起来挺有道理

我们设 \(sg_{l, j}\)（因为简化题意其实是有 SG 函数得到）表示 \([l, l + 2^j)\) 内的数的 \(a_i - l\) 的异或和。

考虑转移，那么首先 \(sg_{l, j} = sg_{l, j - 1} \oplus sg_{l + 2^{j - 1}, j - 1}\),然后对于后面这一段的数 \(a_i - l\) 都要加上 \(2^{j - 1}\)，但实际上因为区间长度才 \(2^{j - 1}\)，不会对后面的位产生影响，所以就有（设 \(cnt\) 为 \([l + 2^{j - 1}, l + 2^j)\) 内的数字个数）：

\[sg_{l, j} = \oplus sg_{l, j - 1} \oplus sg_{l + 2^{j - 1}, j - 1} \oplus ([cnt \!\! \mod 2] \times 2^{j - 1}) \]

同理，查询时从高位到低位枚举进行分解，就不会有影响，只是每个数前面加上一个前缀而已。

时间复杂度：\(O(q \log m)\)

很巧妙的使用倍增避免加减法进位的影响。