萌新刚学Splay 20分求助大佬/kk

\color{red}\text{评测记录}

#include<bits/stdc++.h>
using namespace std;
#define MAXN 2000005 
#define INF 999999999
#define gen e[0].ch[1]
int m,q,n,po,last,zans; 
struct node{
    int ch[2],v,re,sum,fa;
}e[MAXN];
int read(){
    int w=0;
    char c=getchar();
    while (c>'9'||c<'0') c=getchar();
    while (c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+(c^48);
        c=getchar();
    }
    return w;
} 
void addpo(int x,int fa){
    e[++n].fa=fa,e[n].re=e[n].sum=1,e[n].v=x;
}
bool rship(int x){ return e[e[x].fa].ch[1]==x; }
void con(int son,int fa,bool lr){
    e[son].fa=fa,e[fa].ch[lr]=son;
}
void ch(int x){ e[x].sum=e[e[x].ch[0]].sum+e[e[x].ch[1]].sum+e[x].re;}
void turn(int x){
    int y=e[x].fa,ygen=e[y].fa,xship=rship(x),yship=rship(y),B=e[x].ch[xship^1];
    con(B,y,xship);con(y,x,xship^1);con(x,ygen,yship); 
    ch(y);ch(x);
}
void splay(int at,int to){
    to=e[to].fa;
    while (e[at].fa!=to){
        int up=e[at].fa;
        if (e[up].fa==to) turn(at);
        else if (rship(up)==rship(at)) turn(up),turn(at);
        else turn(at),turn(at);
    }
}
void push(int x){
    po++;
    if (po==1){
        gen=n+1;
        addpo(x,0);
    }else{
        int now=gen;
        while (1){
            e[now].sum++;
            if (e[now].v==x){
                e[now].re++;
                splay(now,gen);
                return;
            }
            bool next=e[now].v<x;
            if (!e[now].ch[next]){
                addpo(x,now);
                e[now].ch[next]=n;
                splay(n,gen);
                return;
            }
            now=e[now].ch[next];
        }
    }
}
int find(int x){
    int now=gen;
    while (1){
        if (e[now].v==x){
            splay(now,gen);
            return now;
        }
        bool next=e[now].v<x;
        if (!e[now].ch[next]) return 0;
        now=e[now].ch[next];
    }
}
void kill(int x){ 
    e[x].ch[0]=e[x].ch[1]=e[x].fa=e[x].re=e[x].sum=e[x].v=0; 
    if (x==n) n--;
}
void pop(int x){
    int deal=find(x);
    if (!deal) return;
    po--;
    if (e[deal].re>1){
        e[deal].sum--,e[deal].re--;
        return;
    }
    if (!e[deal].ch[0]){
        gen=e[deal].ch[1];
        e[gen].fa=0;
    }else{
        int l=e[deal].ch[0],r=e[deal].ch[1];
        while (e[l].ch[1]) l=e[l].ch[1];
        splay(l,e[deal].ch[0]);
        con(r,l,1);con(l,0,1);ch(l);
    }
    kill(deal);
}
int arank(int x){
    int now=gen,ans=0;
    while (1){
        if (e[now].v==x){
            ans+=e[e[now].ch[0]].sum+1;
            splay(now,gen);
            return ans;
        }
        if (now==0) return ans+1;
        if (x<e[now].v){
            now=e[now].ch[0];
        }else{
            ans+=e[e[now].ch[0]].sum+e[now].re;
            now=e[now].ch[1];
        }
    }
}
int rerank(int x){
    int now=gen;
    while (1){
        int cha=e[e[now].ch[0]].sum+e[now].re;
        if (x>e[e[now].ch[0]].sum&&x<=cha){
            splay(now,gen);
            return e[now].v;
        }
        if (x<cha) now=e[now].ch[0];
        else x-=cha,now=e[now].ch[1];
    }
}
int low(int x){
    int now=gen,ans=-INF;
    while (now){
        if (x>e[now].v&&e[now].v>ans) splay(now,gen),ans=e[now].v;
        if (e[now].v>=x) now=e[now].ch[0];
        else now=e[now].ch[1];
    }
    return ans;
}
int upp(int x){
    int now=gen,ans=INF;
    while (now){
        if (x<e[now].v&&e[now].v<ans) splay(now,gen),ans=e[now].v;
        if (e[now].v<=x) now=e[now].ch[1];
        else now=e[now].ch[0];
    }
    return ans;
}
int main(){
    m=read();q=read();
    for (int i=1;i<=m;i++){
        push(read());
    }
    while (q--){
        int op=read(),x=read()^last;
        if (op==1) push(x);
        else if (op==2) pop(x);
        else{
            if (op==3) last=arank(x);
            else if (op==4) last=rerank(x);
            else if (op==5) last=low(x);
            else last=upp(x);
            zans^=last;
        } 
    }
    printf("%d\n",zans);
    return 0;
}

万分感谢！