题解 P8257【[CTS2022] 普罗霍洛夫卡】

· · 题解

P8257 [CTS2022] 普罗霍洛夫卡 解题报告：

更好的阅读体验

题意

给定序列 a，m 次查询一个区间所有的子区间颜色数量异或和。

## 分析 扫描线一下就变成了区间加一，区间历史版本异或和查询。 异或具有自反性，一个全部是 $x$ 的段异或值要么是 $0$ 要么是 $x$，也就是我们可以在修改的时候更新历史版本异或和，查询的时候单独处理最后一次就好了。 手玩一下可以得到，对 $x$ 加一，值会异或上 $2^{\text{lowbit}(x)+1}-1$。 再仔细观察一下，可以发现我们维护的序列递增，且相邻最多差 $1$。于是我们以块长 $B=2^k$ 对序列分块，散块暴力重构，可以发现整块进行 $B$ 次整体加一，某个位置异或的值大于 $B$ 的事件只会发生 $B$ 次，那么每个块暴力维护这些事件均摊是 $O(1)$ 的。 而异或的值小于 $B$ 的修改可以考虑提前预处理出结果，每个块维护一下整体加标记。直接预处理复杂度肯定不对，我们可以类似 sos dp 做到 $B+\frac{B}{2}+\frac{B}{4}+\cdots=O(B)$ 的复杂度。 查询很简单，于是就做到了 $O(n\sqrt n)$ 的时空复杂度，不难发现逐块处理空间可以做到线性。 ## 代码 咕了，有时间写。