自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:13:12，当前版本为作者最后更新于2019-11-27 17:56:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

可能更好的体验

在我通过前，这题的正确代码都非常长而且思路比较复杂（也许）。这里说一种简单且易于理解的方法。

考虑到 $m$ 比较小，询问的时候又只考虑最后 $m$ 个二进制位，所以相当于对 $2^m$ 取模。所以数的种类只有 $2^m$ 种，是一个很小的范围。

异或运算是满足消去律的，所以如果一个数 $x$ 对答案产生了贡献，当且仅当它在区间中出现次数为奇数。

我们考虑用bitset维护一个数在一段区间中的出现次数。那么合并相邻两个区间的信息，只需要将两个bitset异或起来即可。

用线段树维护这些bitset，单次查询的时间复杂度为 $O(\frac{2^m}{\omega}\log n)$。

考虑对区间整体加上某个数对bitset的影响。那么，原来的第 $k$ 位的信息，现在对应的就是第 $(k+x)\bmod2^{m}$ 位的信息了。相当于整体左移了 $x$ 位，再把前面那些大于等于 $2^m$ 的右移 $2^m$ 位，并合并起来。当 $m=10$ 时，这里就可以写成b=(b<<x)|(b>>(1024-x))。

这里更新一个节点的信息是 $O(\frac{2^m}{\omega})$ 的，在线段树上区间修改时，单次复杂度还要乘上 $\log n$。区间修改打标记即可。

最后要得到答案，我们有了一个长度为 $2^m$ 的bitset，可以 $O(2^m)$ 判断并计算每位的贡献。

于是得到了一个时间复杂度 $O(\frac{2^m(n+q)\log n}{\omega}+2^mq)$，空间复杂度 $O(2^mn)$ 的算法。

其中，后面的 $O(2^mq)$ 的查询，可以通过预处理，然后手写bitset并每 $32$ 位一起求答案，这样可以优化到 $O(\frac{2^mq}{\omega})$。而 STL 的bitset没法直接提取多位信息（我不太会的说）。不过由于时间复杂度瓶颈不在这里，所以使用 STL 的效率也是可以接受的。

这样做的话，可能会因为常数问题而过不去。注意到当区间比较小的时候，区间里的数很少，此时使用bitset进行运算是非常不划算的，因此在区间比较小的时候，进行暴力修改和查询。

这样就可以通过了，代码长度为 $1.7\rm KB$ 左右。

Code：

#include<iostream>
#include<bitset>
using namespace std;
typedef bitset<1024>BitSet;
const int N=1e5+6;
BitSet d[N];int tg[N],n,m,q,a[N];
void build(int l,int r,int o){
	if(r-l+1<=64){
		for(register int i=l;i<=r;++i)cin>>a[i],d[o].flip(a[i]);
	}else{
		const int mid=l+r>>1;
		build(l,mid,o<<1),build(mid+1,r,o<<1|1);
		d[o]=d[o<<1]^d[o<<1|1];
	}
}
inline void pushdown(int o){
	int&x=tg[o];
	d[o<<1]=(d[o<<1]<<x)|(d[o<<1]>>(1024-x));
	d[o<<1|1]=(d[o<<1|1]<<x)|(d[o<<1|1]>>(1024-x));
	(tg[o<<1]+=x)&=1023,(tg[o<<1|1]+=x)&=1023;
	x=0;
}
void modify(int l,int r,int o,const int&L,const int&R,const int&x){
	if(r-l+1<=64){
		const int lx=max(l,L),rx=min(r,R);
		for(register int i=lx;i<=rx;++i)d[o].flip((a[i]+tg[o])&1023),d[o].flip((tg[o]+((a[i]+=x)&=1023))&1023);
	}else
	if(L<=l&&r<=R){
		d[o]=(d[o]<<x)|(d[o]>>(1024-x));
		(tg[o]+=x)&=1023;
	}else{
		if(tg[o])pushdown(o);
		const int mid=l+r>>1;
		if(L<=mid)modify(l,mid,o<<1,L,R,x);
		if(mid<R)modify(mid+1,r,o<<1|1,L,R,x);
		d[o]=d[o<<1]^d[o<<1|1];
	}
}
void query(int l,int r,int o,const int&L,const int&R,BitSet&b){
	if(r-l+1<=64){
		const int lx=max(l,L),rx=min(r,R);
		for(register int i=lx;i<=rx;++i)b.flip((a[i]+tg[o])&1023);
	}else
	if(L<=l&&r<=R)b^=d[o];else{
		if(tg[o])pushdown(o);
		const int mid=l+r>>1;
		if(L<=mid)query(l,mid,o<<1,L,R,b);
		if(mid<R)query(mid+1,r,o<<1|1,L,R,b);
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	build(1,n,1);
	while(q--){
		int l,r,op,x;
		cin>>op>>l>>r;
		if(op==1){
			cin>>x;
			modify(1,n,1,l,r,x);
		}else{
			static BitSet b;
			b.reset();
			query(1,n,1,l,r,b);
			int ans=0;
			for(register int i=0;i<1024;++i)
				ans^=b[i]*i;
			ans&=(1<<m)-1;
			cout<<ans<<'\n';
		}
	}
	return 0;
}