题解 P8257(CTS2022 T1)

· · 题解

下文假设 n,m 同阶。

问题可以转化 n 次 3-side 矩形加 1，m 次矩阵异或和查询，查询在修改后。

如果我们扫描线一下，就转化成 n 次区间加 1，m 次区间历史异或和查询。

注意到一个很好的性质是 x\oplus x=0，考虑在修改时将之前的值计入历史异或和，最后一次修改后的值是否计入答案在询问时判断。

我们可以同时维护 f_x 和 g_x 为奇数时刻和偶数时刻查询 x 的历史异或和的值，每次修改将其中一个异或 a_i\oplus(a_i+1)=2^{h(a_i)}-1。

然后这个东西似乎还是很难整体维护，我们考虑另一条性质：序列递增且相邻数的差不超过 1。

因为相邻数的差不超过 1，所以在一块里，同一次操作中只有一个数异或的值会大于 B。

对于所有 h(a_i)\leq \log B 的数，我们可以开桶维护后 i 位为 j 的数字数量，这样单次整块修改和下放的复杂度就都是 O(\sqrt{n\log n}) 了。

但是事实上我们的每个操作相当于将后 i 位为 j 的数全部异或上 k，这个东西是可以做到 B+\frac{B}{2}+\frac{B}{4}+\cdots=O(\sqrt n) 的。

然后对于异或值大于 B 的数，我们记录每个区间，在每次修改的时候暴力更新，同一个块 \sqrt n 次修改的均摊时间复杂度是 O(\sqrt n) 的。

于是做完了，时间复杂度 O(n\sqrt n)，实现的时候要比较小心，可能一不小心就带上一个 \log 了。

我的程序写的比较丑，似乎在 B=256 的时候比 B=512 快。

如果您没有听懂我在胡扯什么可以私信找我要一下代码，可能代码比我在这瞎扯的东西好理解（