权值线段树 92 pts 求调

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6;
const int L=0;
const int R=1073741823;
int lc[30*N+1],rc[30*N+1];
ll num[30*N+1];
int rt,idx;
void pushup(int p)
{
	num[p]=num[lc[p]]+num[rc[p]];
}
ll query_sum(int p,int x,int y,int l,int r)
{
	if(x<=l&&r<=y)
	{
		return num[p];
	}
	int mid=l+r>>1;
	int sum=0;
	if(x<=mid) sum+=query_sum(lc[p],x,y,l,mid);
	if(y>mid) sum+=query_sum(rc[p],x,y,mid+1,r);
	return sum;
}
int query_id(int p,int l,int r,int k)
{
	if(!p) return -1;
	if(l==r) return l;
	int mid=l+r>>1;
	int ans=-1;
	if(k<=num[lc[p]])
	{
		ans=query_id(lc[p],l,mid,k);
	}
	else
	{
		ans=query_id(rc[p],mid+1,r,k-num[lc[p]]);
	}
	return ans;
}
void update(int &p,int x,int y,int l,int r,int k)
{
	if(!p) p=++idx;
	if(x<=l&&r<=y)
	{
		num[p]+=(r-l+1)*k;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) update(lc[p],x,y,l,mid,k);
	if(y>mid) update(rc[p],x,y,mid+1,r,k);
	pushup(p);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n,q;
	cin>>n>>q;
	int lst=0,ans=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		update(rt,x,x,L,R,1);
	}
	while(q--)
	{
		int t,x;
		cin>>t>>x;
		x^=lst;
		if(t==1)
		{
			update(rt,x,x,L,R,1);
		}
		else if(t==2)
		{
			update(rt,x,x,L,R,-1);
		}
		else if(t==3)
		{
			int cur=query_sum(1,L,x-1,L,R)+1;
			ans^=cur;
			lst=cur;
		}
		else if(t==4)
		{
			int cur=query_id(1,L,R,x);
			ans^=cur;
			lst=cur;
		}
		else if(t==5)
		{
			int cur=query_id(1,L,R,query_sum(1,L,x-1,L,R));
			ans^=cur;
			lst=cur;
		}
		else if(t==6)
		{
			int cur=query_id(1,L,R,query_sum(1,L,x,L,R)+1);
			ans^=cur;
			lst=cur;
		}
	}
	cout<<ans;
	return 0;
}