自动搬运

查看原文

来自洛谷，原作者为

	dead_X Still we rise

搬运于2025-08-24 22:37:24，当前版本为作者最后更新于2022-04-04 09:06:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

下文假设 $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$ 快。

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