WBLT 96ptsMLE 求调

#include<bits/stdc++.h>
using namespace std;
template<typename T>
struct WBLT{
    private:
        double alpha=0.25;
        struct node{T v;int s;node*l,*r;}*root;
        bool leaf(node*p){return!p->l&&!p->r;}
        int size(node*p){return p?p->s:0;}
        void update(node*p){
            if(leaf(p))p->s=1;
            else p->s=size(p->l)+size(p->r),p->v=p->r->v;
        }node*merge(node*l,node*r){
            node*p=new node{0,0,l,r};
            update(p);return p;
        }void rotate(node*&p,bool d){
            if(!d){
                p->r=merge(p->l->r,p->r);
                p->l=p->l->l;
            }else{
                p->l=merge(p->l,p->r->l);
                p->r=p->r->r;
            }
        }void maintain(node*&p){
            if(leaf(p))return;
            if(size(p->l)*alpha>size(p->r))rotate(p,0);
            else if(size(p->r)*alpha>size(p->l))rotate(p,1);
            if(size(p->l)*alpha>size(p->r))rotate(p->l,1),rotate(p,0);
            else if(size(p->r)*alpha>size(p->l))rotate(p->r,0),rotate(p,1);
        }inline void insert(node*&p,T v){
            if(leaf(p)){
                p->l=new node{min(v,p->v),1,0,0};
                p->r=new node{max(v,p->v),1,0,0};
            }else if(p->l->v>=v)insert(p->l,v);
            else insert(p->r,v);
            update(p);maintain(p);
        }inline void erase(node*&p,T v){
            if(p->l->v>=v){
                if(leaf(p->l)){
                    node*t=p;delete p->l;
                    p=p->r;delete t;return;
                }else erase(p->l,v);
            }else{
                if(leaf(p->r)){
                    node*t=p;delete p->r;
                    p=p->l;delete t;return;
                }else erase(p->r,v);
            }update(p);maintain(p);
        }
    public:
        WBLT():root(new node{INT_MAX,1,0,0}){}
        void insert(T v){insert(root,v);}
        void erase(T v){erase(root,v);}
        int order_of_key(T v){
            node*p=root;int ans=0;
            while(p){
                if(leaf(p))return ans+1;
                else if(p->l->v>=v)p=p->l;
                else ans+=size(p->l),p=p->r;
            }return 1;
        }T find_by_order(int k){
            node*p=root;
            while(p){
                if(leaf(p))return k==1?p->v:T();
                else if(size(p->l)>=k)p=p->l;
                else k-=size(p->l),p=p->r;
            }return T();
        }T pre(T v){return find_by_order(order_of_key(v)-1);}
        T suc(T v){return find_by_order(order_of_key(v+1));}
};WBLT<int>tr;int n,m,lst,t,x,ans;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>x,tr.insert(x);
    while(m--){
        cin>>t>>x;x^=lst;
        if(t==1)tr.insert(x);
        else if(t==2)tr.erase(x);
        else if(t==3)lst=tr.order_of_key(x),ans^=lst;
        else if(t==4)lst=tr.find_by_order(x),ans^=lst;
        else if(t==5)lst=tr.pre(x),ans^=lst;
        else if(t==6)lst=tr.suc(x),ans^=lst;
    }cout<<ans;
}