本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 21:44:59

核桃周赛搬的，已严肃学习 hhoppitree 题解做法，记录一下。

题意

给定序列 $a$，$q$ 次询问 $[L,R]$ 内所有子区间权值异或和，区间权值定义为该区间内数字种类数。$n,q\le 4\times 10^5$，时间限制 $10$ 秒。

题解

询问所有子区间考虑离线，按照右端点排序后扫描，并维护每个点到当前点的种类数 $c_i$。扫到询问右端点 $R$ 时，$[L,R]$ 的区间历史异或和即为答案。然而历史异或和还是太难了，考虑避免历史和。注意到若 $t$ 时刻 $c_i$ 未修改，则 $t-1,t$ 两时刻的 $c_i$ 相等，异或后会抵消掉。因此从后往前每两个时刻一起算，则 $t-1,t$ 会贡献当且仅当 $ c_i$ 在 $t$ 时刻被修改，贡献值为 $c_{i,t-1}\oplus(c_{i,t-1}+1)$。

将该贡献放到 $t$ 时刻上，则历史和变成了奇偶性相同的若干时刻异或和。因此设 $b_{i,0/1}$ 表示目前 $i$ 处所有偶数 / 奇数时刻的总贡献，$t$ 时刻修改即区间内 $b_{i,t\bmod 2}$ 异或上 $c_i\oplus(c_i+1)$，之后 $c_i$ 加一；查询即求区间 $b_{i,R\bmod 2}$ 的异或和，这样就没有历史和了。

注意到 $c_i\oplus(c_i+1)$ 的值只与 $c_i$ 末尾 $1$ 的个数 $k$ 有关，该值为 $2^{k+1}-1$，因此大部分贡献值都很小。考虑根号分治，以 $2^B$ 为界划分，则当且仅当 $c_i$ 后 $B$ 位均为 $1$ 时贡献值会超过 $2^B-1$，而这每加 $2^B$ 才会发生一次，每个位置只会发生 $\frac n{2^B}$ 次，在 $B$ 足够大时即可暴力修改。

因此现在只需快速维护 $b$ 数组后 $B$ 位的值。考虑对原序列每 $S$ 个元素分一块，修改时对整块打标记并整体改动，散块下传标记后暴力修改，查询也是类似的，问题在于如何支持整体改。由于只考虑后 $B$ 位，可对每个块预处理出 $w_{i,v}$，表示 $i$ 块在 $tag\bmod 2^B=v$ 时再操作一次对后 $B$ 位的贡献。对该贡献拆位，则当且仅当 $(c_i+v)$ 的后 $j$ 位均为 $1$ 时会产生 $2^j$ 的贡献，此时 $(c_i+v)\bmod 2^j=2^j-1$，即 $c_i$ 与 $v$ 后 $j$ 位互为补集。

考虑从低位到高位对所有 $c_i$ 后 $B$ 位建立 Trie 树，求 $w_{i,v}$ 时在 Trie 树上找到 $2^B-1-(v\bmod 2^B)$ 这条路径，则其第 $j$ 层节点子树内均满足后 $j$ 位与 $v$ 互为补集，这些 $(c_i+v)$ 会产生 $2^j$ 贡献，因此当且仅当该子树大小为奇数时 $2^j$ 位为 $1$。由于只关心子树大小，可预先建出树，$c_i$ 直接贡献到叶子节点，之后遍历整棵 Trie 即可求出所有 $w_{i,v}$，时间复杂度单次 $O(2^B)$。整块修改时即可直接将值异或上 $w_{i,tag_i}$，再将 $tag_i$ 加一。

另外需支持迅速找到整块内目前 $c_i+tag\equiv {2^B-1}\pmod {2^B}$ 的所有位置，从而暴力更新高位信息。这需要在构建块时将所有 $c_i$ 按照 $c_i\bmod 2^B$ 排序，并记录每种值的区间，可以使用桶排。这样修改时只需要找到 $2^B-1-(tag\bmod 2^B)$ 对应的区间，暴力修改其中所有位置即可。要注意这种修改不能影响到后 $B$ 位，后 $B$ 位的贡献是单独计算的。这样整个重构操作就做完了，单次复杂度 $O(2^B+S)$，常数比较大。

还需要解决标记下传问题，$c_i$ 的更新是简单的，然而还需要更新所有 $b$ 的值。考虑同样拆位算贡献，对所有 $v\lt 2^B$ 记录下该块在 $tag=v$ 情况下操作次数的奇偶性。下传时将所有奇数次的 $v$ 放到 Trie 上，再查询 $2^B-1-(c_i\bmod 2^B)$ 即可，单次复杂度同样是 $O(2^B+S)$。

分析出来总复杂度为 $O(\frac{n^2}{2^B}+(n+q)(S+2^B+\frac {n^2}S))$，取 $2^B\pprox S=\sqrt n$ 可以得到理论最优复杂度 $O((n+q)\sqrt n)$。然而其中 $2^B$ 常数极大，实践发现取 $B=7,2^B=128$ 跑得最快。另外 $S$ 与 $B$ 是独立的，但实践下来发现同样取 $S=128$ 还是比较优的，因此下面的代码取了该块长。

代码

#include<iostream>
#include<vector>
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=4e5+10;
const int B=128;
const int M=B+10;
const int K=N\/B+10;
int n,m,a[N],res[N],last[N],lp[N],lg[M],tp[M],id[N],L[K],R[K],c[N];
int tag[K],b[2][N],s[2][K],w[K][M],fp[K][M],po[K][M],g[2][M<<1];
bool t[K][2][M],ct[M<<1]; \/\/ t 也是标记，记录每个块每种值操作次数的奇偶性 
vector <pii> ask[N];
void build(int u,int d,int x)
{
	if((1<<d)==B) {tp[x]=u; return;}
	lg[u]=d,build(u<<1,d+1,x),build(u<<1|1,d+1,x|(1<<d));
} \/\/ 建出 B 位的 Trie，并预处理每种值的位置 tp_x 
void built(int id)
{
	s[0][id]=s[1][id]=0;
	for(int i=0;i<=B;i++)
	{
		w[id][i]=fp[id][i]=0;
		for(int o=0;o<2;o++) t[id][o][i]=0;
	} \/\/ 清空原信息 
	for(int i=0;i<(B<<1);i++) ct[i]=0;
	for(int i=L[id];i<=R[id];i++)
	{
		s[0][id]^=b[0][i],s[1][id]^=b[1][i];
		ct[tp[c[i]&(B-1)]]^=1,fp[id][B-1-(c[i]&(B-1))]++;
	}
	for(int i=1;i<=B;i++) fp[id][i]+=fp[id][i-1];
	for(int i=L[id];i<=R[id];i++) po[id][--fp[id][B-1-(c[i]&(B-1))]]=i; \/\/类似桶排用 po 按值排序记录所有位置，fp 记录每种值的左端点 
	for(int i=B-1;i;i--) ct[i]=(ct[i<<1]^ct[i<<1|1]);
	g[0][1]=ct[1];
	for(int i=2;i<(B<<1);i++)
	{
		g[0][i]=g[0][i>>1];
		if(i<B) g[0][i]|=(ct[i]<<lg[i]);
	}
	for(int i=0;i<B;i++) w[id][i]=g[0][tp[B-1-(i&(B-1))]]; \/\/ 用 Trie 计算贡献数组 w  
}
void push(int id)
{
	for(int o=0;o<2;o++)
	{
		for(int i=0;i<(B<<1);i++) ct[i]=0;
		for(int i=0;i<B;i++) ct[tp[i]]^=t[id][o][i];
		for(int i=B-1;i;i--) ct[i]=(ct[i<<1]^ct[i<<1|1]);
		g[o][1]=ct[1];
		for(int i=2;i<(B<<1);i++)
		{
			g[o][i]=g[o][i>>1];
			if(i<B) g[o][i]|=(ct[i]<<lg[i]);
		}
	}
	for(int i=L[id];i<=R[id];i++)
	{
		for(int o=0;o<2;o++) b[o][i]^=g[o][tp[B-1-(c[i]&(B-1))]];
		c[i]+=tag[id];
	} \/\/ 同样用 Trie 进行 c 值的更新 
	tag[id]=0;
}
void pt(int o,int id)
{
	int v=(tag[id]&(B-1)); tag[id]++;
	s[o][id]^=w[id][v],t[id][o][v]^=1;
	for(int i=fp[id][v];i<fp[id][v+1];i++)
	{
		int p=po[id][i],d=((c[p]+tag[id])^(c[p]+tag[id]-1)^(B-1));
		s[o][id]^=d,b[o][p]^=d;
	}  \/\/ 暴力操作对高位产生影响的位置 
} \/\/ 操作一个整块 
void update(int o,int l,int r)
{
	int pl=id[l],pr=id[r];
	if(pl==pr)
	{
		push(pl);
		for(int i=l;i<=r;i++) c[i]++,b[o][i]^=c[i]^(c[i]-1);
		built(pl);
	}
	else
	{
		push(pl),push(pr);
		for(int i=l;i<=R[pl];i++) c[i]++,b[o][i]^=c[i]^(c[i]-1);
		for(int i=L[pr];i<=r;i++) c[i]++,b[o][i]^=c[i]^(c[i]-1);
		for(int i=pl+1;i<pr;i++) pt(o,i);
		built(pl),built(pr);
	}
}
int query(int o,int l,int r)
{
	int tr=0,pl=id[l],pr=id[r];
	if(pl==pr)
	{
		push(pl),built(pl);
		for(int i=l;i<=r;i++) tr^=b[o][i];
	}
	else
	{
		push(pl),push(pr),built(pl),built(pr);
		for(int i=l;i<=R[pl];i++) tr^=b[o][i];
		for(int i=L[pr];i<=r;i++) tr^=b[o][i];
		for(int i=pl+1;i<pr;i++) tr^=s[o][i];
	}
	return tr;
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m,build(1,0,0);
	for(int i=1;i<=n;i++) cin>>a[i],lp[i]=last[a[i]]+1,last[a[i]]=i,id[i]=(i-1)\/B+1,R[id[i]]=i;
	for(int i=n;i;i--) L[id[i]]=i;
	for(int i=1,l,r;i<=m;i++) cin>>l>>r,ask[r].pb({l,i});
	for(int i=1;i<=n;i++)
	{
		update(i&1,lp[i],i);
		for(pii te:ask[i]) res[te.se]=query(i&1,te.fi,i);
	}
	for(int i=1;i<=m;i++) cout<<res[i]<<'\n';
	return 0;
}