自动搬运

查看原文

来自洛谷，原作者为

	Nangu 加 训

搬运于2025-08-24 22:39:51，当前版本为作者最后更新于2025-03-14 19:34:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我们考虑对 $r$ 进行扫描线。

设当前枚举到右端点 $p$，$a_i$ 表示左端点为 $i$ 时二元组的权值，$b_i$ 表示数组 $a$ 的历史和，则对于询问 $[l, r]$ 答案为 $\bigoplus_{i=l}^r b_i$。

我们需要做的操作：

1. 对于 $i \in [l, r]$，$a_i+1 \to a_i$。
2. 对于 $i \in [1, p]$，$b_i \operatorname{xor} a_i\to b_i$。
3. 查询 $b$ 的区间异或和。

考虑序列分块。我们先预处理出 $f_{o, x}$ 表示第 $o$ 块 $\bigoplus_{i=bl}^{br} {(a_i+x)}$ 的值，其中 $x\le B$。

对于第一类操作：

• 散块：暴力修改，暴力重构。
• 整块：我们维护一个 $tag$ 数组，每次修改整块时 tag[o]++，若 $tag_o=B$，须重构整块。

对于第二类操作：

• 散块：暴力重构。
• 整块：直接令 $sumb_o \operatorname{xor} f_{o, tag_o} \to sumb_o$，同时维护一个桶 $k$，每次将 $tag_o$ 加入 $k_o$，用于维护 $b$。

第三类是平凡的。

现在我们只剩下了一个问题：如何暴力重构整块？

我们需要干两件事：重新计算 $f$ 的值，以及将懒标记下放更新 $b$ 的值。

更新 $b$ 的值相当于对于每一个在桶内的值 $x$，执行 $b_i \operatorname{xor} (a_i+x) \to b_i$。容易发现这个过程和计算 $f$ 的过程非常像，因此我们下文只讨论 $f$ 的处理方法。

注意到 $a+b$ 可以看作 $a\operatorname{xor}b$ 再加上 $a+b$ 所产生的每一个进位。因此，我们可以逐位计算 $f_x$ 的进位的个数，则原问题就转化为求对于每一个 $2$ 的正整数幂 $k$ 以及 $x$，计算 $x \bmod k+ a_i \bmod k \ge k$ 的个数。

这样直接枚举值域并双指针的做法是 $O(B\log n)$ 的，考虑进行一点优化。

我们将 $k$ 分成 $\le B$ 和 $>B$ 两类。

对于第一类 $k$，令 $dp_{k, y}$ 表示 $x \bmod k=y$ 的 $x$ 在 $k$ 上的贡献。这个数组的总元素个数是 $O(B)$ 的。容易线性求出。

对于第二类 $k$，容易发现，此时 $x\bmod k=x$。发现对于任意的 $a_i$，$a_i$ 对一些 $x$ 造成贡献的一定是 $k$ 的一段前缀，且这段前缀里 $x$ 的值域完全相同，于是直接前缀和统计即可。

如果你看到这里一脸蒙逼，请结合下面的代码一起食用。

const int B=511;
void rebuild(const int o){
    const int l=bl[o], r=br[o];
    rep(i, l, r) num[a[i]&B]^=1;//开一个桶
    per(k, 8, 0){
        int s=1<<k+1, now=0;
        rep(i, 1, s-1){
            now^=num[s-i];
            if(now) pre[k][i]=s;//pre[k][i] 表示在 模 2^k 下，i 的贡献
        }
        rep(i, 1, s-1) if(i>>k&1) num[i^1<<k]^=num[i], num[i]=0;
    }
    num[0]=0;
    rep(k, 0, 7){
        const int s=1<<k+1;
        rep(i, 1, s-1){
            pre[k+1][i]^=pre[k][i];
            pre[k+1][i|s]^=pre[k][i];
			//进行前缀和
            pre[k][i]=0;
        }
    }
    rep(i, 0, B) f[o][i]=pre[8][i], pre[8][i]=0;//算出第一部分(x<=B)的贡献
    rep(i, l, r){
        int p=__builtin_ctz((a[i]>>9)^O);
        if(p) num[(1<<10)-(a[i]&1023)]^=(1<<10+p)-(1<<10);
		/* 
		第二部分。
		此时 x<=B<=k/2
		想要让 x+a_i%k>=k，a_i 第10，11，12一直到log2(k)位必须为1
		这就是为什么“贡献一定是一个k的前缀”
		p即为 a_i 的最长连续1段的长度
		*/
    }
    int now=0;
    rep(i, 0, B) now^=num[i], num[i]=0, f[o][i]^=now;
    int s=0;
    rep(i, l, r) s^=a[i];//计算不进位的贡献
    rep(i, 0, B){
        f[o][i]^=s;
        if(r-l+1&1) f[o][i]^=i;
    }
}