自动搬运

查看原文

来自洛谷，原作者为

	irris Good Luck.

搬运于2025-08-24 22:56:14，当前版本为作者最后更新于2024-04-05 23:30:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

根号分治 / 差分

$*1000$，$6.5$。

Preface

这种题为啥不放月赛 1A，搞笑用的？

Solution

对于原序列差分，那么我们不仅易于得到 $b_i$，而且修改易于转化，可以获得显然的 $\mathcal O(nq)$ 做法。

首先如果我们仅仅转化为「区间加 / 减，全局异或和」是不可能做得了的。所以考虑一个长度为 $k$ 的 $a_i \neq a_{i+1}$ 极长区间，它的贡献应当有

• $b_1 \gets b_1 + k$，$b_2 \gets b_2 + (k - 1)$，$\dots$，$b_k \gets b_k + 1$

因此容易发现这是一段等差数列。进一步地，若 $l_1 + l_2 + \dots + l_{p} = n$，显然 $\{l_p\}$ 中不同的元素仅有 $\mathcal O(\sqrt{n})$ 种。

我们将 $l$ 从大到小排序，因此我们说这形成了 $\mathcal O(\sqrt{n})$ 个等差数列（等差数列对应项相加，依旧是等差数列），并且形式看起来比较优美。我们只要能快速计算等差数列的 xor 即可。

对公差 $d$ 根号分治。$d \leq \sqrt{n}$，我们进行预处理；$d > \sqrt{n}$，不会有超过 $\sqrt{n}$ 项，暴力即可。

时空复杂度 $\mathcal O(n\sqrt{n})$。

Postscript

为啥我取 $b = 2$ 没过去。

$b = 50$ 是比较优秀的，直接跑到了最优解 rk2。调参和造数据就留给后人吧。