hdu1752 copy

题目大意

给你一个整数序列$\{a_n\}$,有两种操作,将执行$q$次操作,第一种把$l\sim r$的序列$copy$one insert$r$后,第二种询问$a_x$是什么,要求求出所有$2$XOR and sum of operations
$n,q\le 1e5,l,r,x\le n$

题解

The effect of the first operation on subsequent queries,如果$x\le r$则不变,$x>r$则$x=x-(r-l+1)$
So you can consider working from the back to the front,But still not good
Since the answer asks for XOR and,So the same query can cancel,所以可以用$bitset$维护,The first operation can also be used easily$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;
}