萌新妺子刚学OI求助传统Treap52分

传统有旋 Treap，普通版过了，52 不是 TLE 而是 WA

#include <bits/stdc++.h>
using namespace std;

#define INF 0x7f7f7f7f

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
uniform_int_distribution<> dis(0,INF);

struct TREAP{
    int val,pri;
    int cnt,size;
    int l,r;
}t[2000020];

int cur,root,n,m,last,ansxor;

inline int NEW(int v){
    t[++cur].val=v;
    t[cur].pri=dis(rnd);
    t[cur].cnt=t[cur].size=1;
    return cur;
}//新节点

inline void PUSHUP(int k){
    t[k].size=t[t[k].l].size+t[t[k].r].size+t[k].cnt;
}//更新子树大小

inline void BUILD(){
    NEW(-INF),NEW(INF);
    root=1;
    t[root].r=2;
    PUSHUP(root);
}//建树

inline int GETRNK(int x,int k){
    if(k==0)return 0;
    if(x==t[k].val)return t[t[k].l].size+1;
    if(x<t[k].val)return GETRNK(x,t[k].l);
    if(x>t[k].val)return t[t[k].l].size+t[k].cnt+GETRNK(x,t[k].r);
}//获取排名

inline int GETVAL(int x,int k){
    if(k==0)return INF;
    if(t[t[k].l].size>=x)return GETVAL(x,t[k].l);
    if(t[t[k].l].size+t[k].cnt>=x)return t[k].val;
    return GETVAL(x-t[t[k].l].size-t[k].cnt,t[k].r);
}//获取值

inline void ZIG(int &k){
    int p=t[k].l;
    t[k].l=t[p].r,t[p].r=k,k=p;
    PUSHUP(t[k].r);PUSHUP(k);
}//左旋

inline void ZAG(int &k){
    int p=t[k].r;
    t[k].r=t[p].l,t[p].l=k,k=p;
    PUSHUP(t[k].l);PUSHUP(k);
}//右旋

inline void INSERT(int v,int &k){
    if(k==0){
        k=NEW(v);
        return;
    }
    if(v==t[k].val){
        t[k].cnt++;
        PUSHUP(k);
        return;
    }
    if(v<t[k].val){
        INSERT(v,t[k].l);
        if(t[k].pri<t[t[k].l].pri)
            ZIG(k);
    }else{
        INSERT(v,t[k].r);
        if(t[k].pri<t[t[k].r].pri)
            ZAG(k);
    }
    PUSHUP(k);
}//插入

int GETPRE(int v){
    int ans=1;
    int k=root;
    while(k){
        if(v==t[k].val){
            if(t[k].l){
                k=t[k].l;
                while(t[k].r)
                    k=t[k].r;
                ans=k;
            }
            break;
        }
        if(t[k].val<v&&t[k].val>t[ans].val)
            ans=k;
        k=v<t[k].val?t[k].l:t[k].r;
    }
    return t[ans].val;
}//获取前驱

int GETNXT(int v){
    int ans=2;
    int k=root;
    while(k){
        if(v==t[k].val){
            if(t[k].r){
                k=t[k].r;
                while(t[k].l)
                    k=t[k].l;
                ans=k;
            }
            break;
        }
        if(t[k].val>v&&t[k].val<t[ans].val)
            ans=k;
        k=v<t[k].val?t[k].l:t[k].r;
    }
    return t[ans].val;
}//获取后继

inline void DELETE(int v,int &k){
    if(k==0)return;
    if(v==t[k].val){
        if(t[k].cnt>1){
            t[k].cnt--;
            PUSHUP(k);
            return;
        }
        if(t[k].l||t[k].r){
            if(t[k].r==0||t[t[k].l].pri>t[t[k].r].pri)
                ZIG(k),DELETE(v,t[k].r);
            else 
                ZAG(k),DELETE(v,t[k].l);
            PUSHUP(k);
        }else k=0;
        return;
    }
    v<t[k].val?DELETE(v,t[k].l):DELETE(v,t[k].r);
    PUSHUP(k);
}//删除

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(nullptr);
    BUILD();
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        int tmp;
        cin>>tmp;
        INSERT(tmp,root);
    }  
    while(m--){
        int o,x;
        cin>>o>>x;
        x^=last;
        switch(o){
        case 1:
            INSERT(x,root);
            break;
        case 2:
            DELETE(x,root);
            break;
        case 3:
            last=GETRNK(x,root)-1;
            ansxor^=last;
            break;
        case 4:
            last=GETVAL(x+1,root);
            ansxor^=last;
            break;
        case 5:
            last=GETPRE(x);
            ansxor^=last;
            break;
        case 6:
            last=GETNXT(x);
            ansxor^=last;
            break;
        }
    }
    cout<<ansxor;
    return 0;
}

lz 可能被 whk 作业薄杀了可能回复不及时