动开线段树92pts求条

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int P=1;
struct sgt{
	int ls,rs,sz;
}t[60000005];
int id=1,n,tn=1<<30;
void add(int l,int r,int p,int u,int k){
	t[u].sz+=k;
	if(l==r)return;
	int mid=(l+r)/2;
	if(p<=mid){
		if(!t[u].ls)t[u].ls=++id;
		add(l,mid,p,t[u].ls,k);
	}
	else{
		if(!t[u].rs)t[u].rs=++id;
		add(mid+1,r,p,t[u].rs,k);
	}
}
int getsum(int l,int r,int p,int u){
	if(!u)return 0;
	if(l==r)return t[u].sz;
	int mid=(l+r)/2;
	if(mid+1<=p)return t[t[u].ls].sz+getsum(mid+1,r,p,t[u].rs);
	else return getsum(l,mid,p,t[u].ls);
}
int getnum(int l,int r,int u,int k){
	if(!u)return 0;
	if(l==r)return l;
	if(t[u].ls&&t[t[u].ls].sz>=k)return getnum(l,(l+r)/2,t[u].ls,k);
	else return getnum((l+r)/2+1,r,t[u].rs,k-t[t[u].ls].sz);
}
int a,lst,m;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;int ans=0;
	for(int i=1;i<=n;i++){
		cin>>a;
		add(1,tn,a+P,1,1);
	}
	for(int i=1,op,x;i<=m;i++){
		cin>>op>>x;
		x^=lst;
		if(op==1){
			add(1,tn,x+P,1,1);
		}
		else if(op==2){
			add(1,tn,x+P,1,-1);
		}
		else if(op==3){
			lst=(getsum(1,tn,x+P-1,1)+1);
			ans^=lst;
		}
		else if(op==4){
			lst=getnum(1,tn,1,x)-P;
			ans^=lst;
		}
		else if(op==5){
			lst=getnum(1,tn,1,getsum(1,tn,x+P-1,1))-P;
			ans^=lst;
		}
		else{
			lst=getnum(1,tn,1,getsum(1,tn,x+P,1)+1)-P;
			ans^=lst;
		}
	}cout<<ans;
	return 0;
}