替罪羊树求调

#include<bits/stdc++.h>
#define MAXN (int)2e6+10
#define a 0.7
using namespace std;
int n,m,lstans,ans,bin[MAXN],top,stk[MAXN],tmp,tot,rb,rt;
struct node
{
	int ls,rs,siz,tsiz,val,cnt,sum,fa;
}tr[MAXN];
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
inline int newnode()
{
	if(top)
	{
		return bin[top--];
	}
	return ++tot;
}
inline void del(int k)
{
	tr[k]=(node){0,0,0,0,0,0,0,0};
	bin[++top]=k;
}
inline void update(int k)
{
	tr[k].tsiz=tr[tr[k].ls].tsiz+tr[tr[k].rs].tsiz+!!tr[k].cnt;
	tr[k].siz=tr[tr[k].ls].siz+tr[tr[k].rs].siz+1;
	tr[k].sum=tr[tr[k].ls].sum+tr[tr[k].rs].sum+tr[k].cnt;
}
inline bool bad(int k)
{
	return tr[k].sum&&(a*tr[k].siz<=max(tr[tr[k].ls].siz,tr[tr[k].rs].siz)||a*tr[k].siz>=tr[k].tsiz);
}
inline void dfs(int k)
{
	if(!k)
	{
		return ;
	}
	dfs(tr[k].ls);
	if(tr[k].cnt)
	{
		stk[++tmp]=k;
	}
	dfs(tr[k].rs);
	if(!tr[k].cnt)
	{
		del(k);
	}
}
inline int build(int l,int r,int lst)
{
	int mid=(l+r)>>1,k=stk[mid];
	if(l==r)
	{
		tr[k]=(node){0,0,1,1,tr[k].val,tr[k].cnt,tr[k].cnt,lst};
		return k;
	}
	tr[k].fa=lst;
	if(mid>l)
	{
		tr[k].ls=build(l,mid-1,k);
	}
	else
	{
		tr[k].ls=0;
	}
	tr[k].rs=build(mid+1,r,k);
	update(k);
	return k;
}
inline int rebuild(int k)
{
	tmp=0;
	dfs(k);
	if(tmp)
	{
		return build(1,tmp,tr[k].fa);
	}
	return 0;
}
inline void insert(int &k,int x,int lst)
{
	if(!k)
	{
		k=newnode();
		tr[k]=(node){0,0,1,1,x,1,1,lst};
		return ;
	}
	if(x==tr[k].val)
	{
		tr[k].cnt++;
	}
	else
	{
		if(x<tr[k].val)
		{
			insert(tr[k].ls,x,k);
		}
		else
		{
			insert(tr[k].rs,x,k);
		}
	}
	update(k);
	if(bad(k))
	{
		rb=k;
	}
}
inline void erase(int k,int x)
{
	if(tr[k].val==x)
	{
		tr[k].cnt--;
	}
	else
	{
		if(x<tr[k].val)
		{
			erase(tr[k].ls,x);
		}
		else
		{
			erase(tr[k].rs,x);
		}
	}
	update(k);
	if(bad(k))
	{
		rb=k;
	}
}
inline int findrank(int x)
{
	int ret=1;
	for(int k=rt;k;)
	{
		if(tr[k].val==x)
		{
			ret+=tr[tr[k].ls].sum;
			break;
		}
		if(x<tr[k].val)
		{
			k=tr[k].ls;
		}
		else
		{
			ret+=tr[tr[k].ls].sum+tr[k].cnt;
			k=tr[k].rs;
		}
	}
	return ret;
}
inline int find(int x)
{
	for(int k=rt;k;)
	{
		if(tr[tr[k].ls].sum<x&&tr[tr[k].ls].sum+tr[k].cnt>=x)
		{
			return tr[k].val;
		}
		if(tr[tr[k].ls].sum>=x)
		{
			k=tr[k].ls;
		}
		else
		{
			x-=tr[tr[k].ls].sum+tr[k].cnt;
			k=tr[k].rs;
		}
	}
	return -1;
}
inline void debug(int k=rt)
{
	if(!k)
	{
		return ;
	}
	cout<<tr[k].val<<' '<<tr[k].cnt<<' '<<tr[tr[k].fa].val<<endl;
	debug(tr[k].ls);
	debug(tr[k].rs);
}
inline void check()
{
	if(rb)
	{
		if(rb==rt)
		{
			rt=rebuild(rt);
		}
		else
		{
			if(tr[tr[rb].fa].ls==rb)
			{
				tr[tr[rb].fa].ls=rebuild(rb);
			}
			else
			{
				tr[tr[rb].fa].rs=rebuild(rb);
			}
		}
//		debug();
		rb=0;
	}
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		int x=read();
		insert(rt,x,0);
		check();
	}
	while(m--)
	{
		int opt=read(),x=read();
		x^=lstans;
		switch(opt)
		{
			case 1:
			{
				insert(rt,x,0);
				check();
				break;
			}
			case 2:
			{
				erase(rt,x);
				check();
				break;
			}
			case 3:
			{
				lstans=findrank(x);
				ans^=lstans;
				break;
			}
			case 4:
			{
				lstans=find(x);
				ans^=lstans;
				break;
			}
			case 5:
			{
				lstans=find(findrank(x)-1);
				ans^=lstans;
				break;
			}
			case 6:
			{
				lstans=find(findrank(x+1));
				ans^=lstans;
				break;
			}
		}
	}
	printf("%d",ans);
	return 0;
}