hdu1752 copy

题目大意

给你一个整数序列$\{a_n\}$，有两种操作，将执行$q$次操作，第一种把$l\sim r$的序列$copy$一份插到$r$后，第二种询问$a_x$是什么，要求求出所有$2$操作的异或和
$n,q\le 1e5,l,r,x\le n$

题解

第一种操作对后续询问的影响，如果$x\le r$则不变，$x>r$则$x=x-(r-l+1)$
所以可以考虑从后往前进行操作，但是还是不好做
由于答案要求异或和，所以相同询问可以抵消，所以可以用$bitset$维护，第一种操作也可以很轻松地用$bitset$实现

code

#include<cstdio>
#include<bitset>
#include<iostream>
using namespace std;
void read(int &res)
{
    
	res=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while('0'<=ch&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
}
const int N=1e5;
int n,q,a[N+10],opt[N+10],x[N+10],y[N+10];
bitset<N> dp,low,high;
int main()
{
    
	int T;
	read(T);
	for(;T--;)
	{
    
		read(n),read(q);
		for(int i=0;i<n;i++) read(a[i]);
		for(int i=1;i<=q;i++)
		{
    
			read(opt[i]),read(x[i]);
			if(opt[i]==1) read(y[i]);
			x[i]--,y[i]--; 
		}
		dp.reset();
		for(int i=q;i>=1;i--)
		{
    
			if(opt[i]==1) high=dp>>y[i]+1,low=dp<<N-y[i]-1>>N-y[i]-1,dp=low^(high<<x[i]);
			else dp.flip(x[i]);
		}
		int ans=0;
		for(int i=0;i<n;i++) if(dp[i]) ans^=a[i];
		printf("%d\n",ans);
	}
	return 0;
}