取随机数的方法是在题解区找的，他也写的是 FHQ Treap。所以这个随机数应该能通过本题。

本代码是从弱化版改动而来的，核心部分可以通过弱化版题目。

#include<bits/stdc++.h>
#define getchar() (p1==p2&&(p2=(p1=buffer)+fread(buffer,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;

const int N=1100005;

int n,m,opt,X,cnt,rt,x,y,z,lst,ret,seed=1;
char buffer[1<<21],*p1,*p2;

struct FHQ_Treap{
	int l,r,val,key,siz;
	FHQ_Treap(){
		l=r=val=key=siz=0;
	}
}fhq[N];

int rnd(){
	return seed*=19260817;
}

int read(){
	int x=0;
	char ch=getchar();
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57){
		x=x*10+(ch^48);
		ch=getchar();
	}
	return x;
}

void newnode(int v){
	fhq[++cnt].val=v;
	fhq[cnt].key=rnd();
	fhq[cnt].siz=1;
}

void upd(int x){
	fhq[x].siz=fhq[ fhq[x].l ].siz+fhq[ fhq[x].r ].siz+1;
}

void split(int rt,int val,int&x,int&y){
	if(!rt)return x=y=0,void();
	if(fhq[rt].val<=val)
		split(fhq[x=rt].r,val,fhq[rt].r,y);
	else split(fhq[y=rt].l,val,x,fhq[rt].l);
	if(x)upd(x);
	if(y)upd(y);
}

int merge(int x,int y){
	if(!x||!y)return x+y;
	if(fhq[x].key>fhq[y].key){
		fhq[x].r=merge(fhq[x].r,y);
		upd(x);
		return x;
	}
	fhq[y].l=merge(x,fhq[y].l);
	upd(y);
	return y;
}

void ins(int val){
	newnode(val);
	if(!rt)return rt=1,void();
	split(rt,val,x,y);
	rt=merge(merge(x,cnt),y);
}

void del(int val){
	split(rt,val,x,z);
	split(x,val-1,x,y);
	y=merge(fhq[y].l,fhq[y].r);
	rt=merge(merge(x,y),z);
}

int getrank(int val){
	split(rt,val-1,x,y);
	int ret=fhq[x].siz+1;
	rt=merge(x,y);
	return ret;
}

int getnum(int rank){
	int now=rt;
	while(now){
		if(fhq[ fhq[now].l ].siz+1==rank)
			return fhq[now].val;
		if(fhq[ fhq[now].l ].siz>=rank)
			now=fhq[now].l;
		else{
			rank-=fhq[ fhq[now].l ].siz+1;
			now=fhq[now].r;
		}
	}
}

int pre(int val){
	split(rt,val-1,x,y);
	int now=x;
	while(fhq[now].r)
		now=fhq[now].r;
	int ret=fhq[now].val;
	rt=merge(x,y);	
	return ret;
}

int nxt(int val){
	split(rt,val,x,y);
	int now=y;
	while(fhq[now].l)
		now=fhq[now].l;
	int ret=fhq[now].val;
	rt=merge(x,y);
	return ret;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		ins(read());
	while(m--){
		opt=read(),X=read();
		X^=lst;
		switch(opt){
			case 1:
				ins(X);
				break;
			case 2:
				del(X);
				break;
			case 3:
				ret^=(lst=getrank(X));
				break;
			case 4:
				ret^=(lst=getnum(X));
				break;
			case 5:
				ret^=(lst=pre(X));
				break;
			case 6:
				ret^=(lst=nxt(X));
				break;
		}
	}
	cout<<ret;
}