40分treap

#include<bits/stdc++.h>
using namespace std;
int n,tot,root,inf=2147483647;
struct mc{
    int l,r,val,date,cnt,size;
    #define ls(p) a[p].l
    #define rs(p) a[p].r
}a[2000005];
inline int read()
{
    int x=0;char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(; isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-'0';
    return x;
}
inline void push_up(int p)
{
    a[p].size=a[ls(p)].size+a[rs(p)].size+a[p].cnt;
}
inline int newn(int val)
{
    a[++tot].val=val;
    a[tot].date=rand(); 
    a[tot].cnt=a[tot].size=1;
    return tot;
}
inline void build()
{
    newn(-inf);newn(inf);
    root=1;a[1].r=2;
    push_up(root);
}
int getrank(int p,int val)
{
    if(!p)return 0;
    if(val==a[p].val)return a[ls(p)].size+1;
    if(val<a[p].val)return getrank(ls(p),val);
    return getrank(rs(p),val)+a[ls(p)].size+a[p].cnt;
}
int getval(int p,int rank)
{
    if(!p)return inf;
    if(a[ls(p)].size>=rank)return getval(ls(p),rank);
    if(a[ls(p)].size+a[p].cnt>=rank)return a[p].val;
    return getval(rs(p),rank-a[ls(p)].size-a[p].cnt);
}
inline void zag(int &p)
{
    int q=rs(p);
    a[p].r=a[q].l;  a[q].l=p;   p=q;
    push_up(p);push_up(ls(p));
}
inline void zig(int &p)
{
    int q=ls(p);
    a[p].l=a[q].r;  a[q].r=p;   p=q;
    push_up(p);push_up(rs(p));
}
inline int getpre(int val)
{
    int ans=1,p=root;
    while(p){
        if(val==a[p].val){
            if(ls(p)){
                p=ls(p);
                while(rs(p))p=rs(p);
                ans=p;
            }
            break;
        }
        if(val>a[p].val&&a[p].val>a[ans].val)ans=p;
        p=val>a[p].val?rs(p):ls(p);
    }
    return a[ans].val;
}
inline int getnext(int val)
{
    int ans=2,p=root;
    while(p){
        if(val==a[p].val){
            if(rs(p)){
                p=rs(p);
                while(ls(p))p=ls(p);
                ans=p;
            }
            break;
        }
        if(val<a[p].val&&a[p].val<a[ans].val)ans=p;
        p=val>a[p].val?rs(p):ls(p);
    }
    return a[ans].val;
}
void insert(int &p,int val)
{
    if(!p){p=newn(val); return;}
    if(val==a[p].val){a[p].cnt++;   push_up(p); return;}
    if(val<a[p].val){
        insert(ls(p),val);
        if(a[p].date<a[ls(p)].date)zig(p);
    }
    else{
        insert(rs(p),val);
        if(a[p].date<a[rs(p)].date)zag(p);
    }
    push_up(p);
}
void erase(int &p,int val)
{
    if(!p)return;
    if(val==a[p].val){
        if(a[p].cnt>1){a[p].cnt--;  push_up(p); return;}
        if(ls(p)||rs(p)){
            if(!rs(p)||a[ls(p)].date>a[rs(p)].date)zig(p),erase(rs(p),val);
            else zag(p),erase(ls(p),val);
            push_up(p);
        }
        else p=0;return;
    }
    val<a[p].val?erase(ls(p),val):erase(rs(p),val);
    push_up(p);
}
int main()
{
    freopen("mc.in","r",stdin);
    register int i;
    int op,x,m,last=0;
    long long ans=0;
    build();
    n=read();m=read(); 
    for(i=1;i<=n;i++)x=read(),insert(root,x);
    for(i=1;i<=m;i++){
        op=read();x=read();
        x^=last;
        if(op==1)insert(root,x);
        if(op==2)erase(root,x);
        if(op==3)last=getrank(root,x),ans^=last;
        if(op==4)last=getval(root,x+1),ans^=last;
        if(op==5)last=getpre(x),ans^=last;
        if(op==6)last=getnext(x),ans^=last;
    }
    printf("%lld",ans);
}

个人感觉没什么大问题，主要是操作3,4没有的情况不是很明白，不知道写的有没有问题

求大佬解疑