代码

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define fir first
#define sec second
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
typedef pair<int,int> pii;
#define N 1100005
struct Fhq_treap
{
	int ch[N][2],val[N],siz[N],rd[N],rt,cnt;
	inline void pushup(int u) {siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+1;}
	int merge(int u,int v)
	{
		if(!u||!v) return u|v;
		if(rd[u]<=rd[v])
		{
			ch[u][1]=merge(ch[u][1],v);
			pushup(u);
			return u;
		}
		else
		{
			ch[v][0]=merge(u,ch[v][0]);
			pushup(v);
			return v;
		}
	}
	pii split(int u,int k)
	{
		if(!u) return mp(0,0);
		if(val[u]<k)
		{
			pii r=split(ch[u][1],k);
			ch[u][1]=r.fir;
			pushup(u);
			return mp(u,r.sec);
		}
		else
		{
			pii r=split(ch[u][0],k);
			ch[u][0]=r.sec;
			pushup(u);
			return mp(r.fir,u);
		}
	}
	void insert(int v)
	{
		pii A=split(rt,v);
		cnt++; val[cnt]=v,siz[cnt]=1,rd[cnt]=rnd();
		rt=merge(merge(A.fir,cnt),A.sec);
	}
	void erase(int v)
	{
		pii A=split(rt,v);
		pii B=split(A.sec,v+1);
		B.fir=merge(ch[B.fir][0],ch[B.fir][1]);
		rt=merge(merge(A.fir,B.fir),B.sec);
	}
	int qrk(int v)
	{
		pii A=split(rt,v);
		int ans=siz[A.fir];
		rt=merge(A.fir,A.sec);
		return ans+1;
	}
	int qval(int u,int v)
	{
		if(siz[ch[u][0]]+1==v) return val[u];
		if(siz[ch[u][0]]<v) return qval(ch[u][1],v-siz[ch[u][0]]-1);
		else return qval(ch[u][0],v);
	}
	inline int qpre(int v)
	{
		return qval(rt,qrk(v)-1);
	}
	inline int qsuf(int v)
	{
		return qval(rt,qrk(v+1));
	}
}tr;
signed main()

	int n,Q; cin>>n>>Q;
	for(int i=1;i<=n;i++) tr.insert(rnd()%1000000000);
	int las=0,ans=0;
	while(Q--)
	{
		int opt=rnd()%6+1,x=(rnd()%1000000000)^las;
		if(opt==1) tr.insert(x);
		else if(opt==2) tr.erase(x);
		else if(opt==3) las=tr.qrk(x);
		else if(opt==4) las=tr.qval(tr.rt,x);
		else if(opt==5) las=tr.qpre(x);
		else las=tr.qsuf(x);
		if(opt>=3) ans^=las;
	}
	cout<<ans<<endl;
	return 0;
}

评测结果