rt，还是这题得用 Treap？（Treap 明天学）

#include<cstdio>
using namespace std;
const int N=1e5+10,M=1e6+10;
int rt,tot,fa[N+M],ch[N+M][2],cnt[N+M],val[N+M],sz[N+M];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline bool get(int x) { return ch[fa[x]][1]==x; }
inline void pushup(int x) {
  if(!x) return;
  sz[x]=cnt[x];
  if(ch[x][0]) sz[x]+=sz[ch[x][0]];
  if(ch[x][1]) sz[x]+=sz[ch[x][1]]; 
}
inline void rotate(int x) {
  int y=fa[x],z=fa[y],k=get(x);
  ch[y][k]=ch[x][k^1],fa[ch[x][k^1]]=y;
  ch[x][k^1]=y,fa[y]=x;
  fa[x]=z;
  if(z) ch[z][ch[z][1]==y]=x;
  pushup(y),pushup(x);
}
inline void splay(int x,int goal=0) {
  while(fa[x]!=goal) {
    int y=fa[x],z=fa[y];
    if(z!=goal) rotate(get(x)==get(y)?y:x);
    rotate(x);
  }
  if(!goal) rt=x;
}
inline void find(int x) {
  int u=rt;
  if(!u) return;
  while(ch[u][x>val[u]]&&x!=val[u]) u=ch[u][x>val[u]];
  splay(u);
}
inline void insert(int x) {
  int u=rt,f=0;
  while(u&&val[u]!=x) f=u,u=ch[u][x>val[u]];
  if(u) cnt[u]++,pushup(u),pushup(f);
  else {
    u=++tot,val[u]=x,sz[u]=cnt[u]=1,fa[u]=f;
    if(f) ch[f][x>val[f]]=u,pushup(f);
    else rt=u;
  }
  splay(u);
}
inline int query_rank(int x) {
  int u=rt,ans=0;
  while(u) {
    if(x<val[u]) u=ch[u][0];
    else {
      ans+=sz[ch[u][0]];
      if(x==val[u]) return splay(u),ans+1;
      ans+=cnt[u],u=ch[u][1];
    }
  }
  return ans+1;
}
inline int query_kth(int x) {
  int u=rt;
  while(true) {
    if(ch[u][0]&&x<=sz[ch[u][0]]) u=ch[u][0];
    else {
      int tmp=sz[ch[u][0]]+cnt[u];
      if(x<=tmp) return val[u];
      x-=tmp,u=ch[u][1];
    }
  }
}
inline int pre(int x) {
  find(x);
  if(val[rt]<x) return rt;
  int u=ch[rt][0];
  while(ch[u][1]) u=ch[u][1];
  return u;
}
inline int succ(int x) {
  find(x);
  if(val[rt]>x) return rt;
  int u=ch[rt][1];
  while(ch[u][0]) u=ch[u][0];
  return u;
}
inline void del(int x) {
  find(x);
  if(cnt[rt]>1) return cnt[rt]--,pushup(rt),void();
  if(!ch[rt][0]&&!ch[rt][1]) return rt=0,void();
  if(!ch[rt][0]||!ch[rt][1]) return rt=ch[rt][0]?ch[rt][0]:ch[rt][1],fa[rt]=0,void();
  int ort=rt,lb=pre(x);
  splay(lb);
  ch[rt][1]=ch[ort][1],fa[ch[ort][1]]=rt;
  pushup(rt);
}
int main() {
  int n=read(),m=read(),lstans=0,ans=0;
  while(n--) insert(read());
  while(m--) {
    int opt=read(),x=read(); x^=lstans;
    //printf("REAL:%d\n",x);
    if(opt==1) insert(x);
    if(opt==2) del(x);
    if(opt==3) lstans=query_rank(x),ans^=lstans;
    if(opt==4) lstans=query_kth(x),ans^=lstans;
    if(opt==5) lstans=val[pre(x)],ans^=lstans;
    if(opt==6) lstans=val[succ(x)],ans^=lstans;
  }
  printf("%d",ans);
  return 0;
}