未加强版AC 加强版RE92求调 替罪羊树

谢谢了

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
const double alpha=0.75;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f)x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0)putchar('-'),write(-x);
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}
struct node{
    int l,r,val;
    int size,fact;
    bool exist;
}tzy[maxn];
int cnt,root;
void newmode(int &now,int val){
    now=++cnt;
    tzy[now].val=val;
    tzy[now].size=tzy[now].fact=1;
    tzy[now].exist=true;
}
bool imbalence(int now){
    if(max(tzy[tzy[now].l].size,tzy[tzy[now].r].size)>tzy[now].size*alpha || 
    tzy[now].size-tzy[now].fact>tzy[now].size*0.3){
        return true;
    }
    return false;
}
std::vector<int> v;
void ldr(int now){
    if(!now){
        return;
    }
    ldr(tzy[now].l);
    if(tzy[now].exist){
        v.push_back(now);
    }
    ldr(tzy[now].r);
}
void lift(int l,int r,int &now){
    if(l==r){
        now=v[l];
        tzy[now].l=tzy[now].r=0;
        tzy[now].size=tzy[now].fact=1;
        return;
    }
    int m=(l+r)>>1;
    while(m&&l<m&&tzy[v[m]].val==tzy[v[m-1]].val){
        m--;
    }
    now=v[m];
    if(l<m){
        lift(l,m-1,tzy[now].l);
    }
    else{
        tzy[now].l=0;
    }
    lift(m+1,r,tzy[now].r);
    tzy[now].size=tzy[tzy[now].l].size+tzy[tzy[now].r].size+1;
    tzy[now].fact=tzy[tzy[now].l].fact+tzy[tzy[now].r].fact+1;
}
void rebuild(int &now){
    v.clear();
    ldr(now);
    if(v.empty()){
        now=0;
        return ;
    }
    lift(0,v.size()-1,now);
}
void update(int now,int end){
    if(!now){
        return;
    }
    if(tzy[end].val<tzy[now].val){
        update(tzy[now].l,end);
    }
    else{
        update(tzy[now].r,end);
    }
    tzy[now].size=tzy[tzy[now].l].size+tzy[tzy[now].r].size+1;
}
void check(int &now,int end){
    if(now==end){
        return;
    }
    if(imbalence(now)){
        rebuild(now);
        update(root,now);
        return;
    }
    if(tzy[end].val<tzy[now].val){
        check(tzy[now].l,end);
    }
    else {
        check(tzy[now].r,end);
    }
}
void ins(int &now,int val){
    if(!now){
        newmode(now,val);
        check(root,now);
        return;
    }
    tzy[now].size++;
    tzy[now].fact++;
    if(val<tzy[now].val){
        ins(tzy[now].l,val);
    }
    else {
        ins(tzy[now].r,val);
    }
}
void del(int now,int val){
    if(tzy[now].exist&&tzy[now].val==val){
        tzy[now].exist=false;
        tzy[now].fact--;
        check(root,now);
        return;
    }
    tzy[now].fact--;
    if(val<tzy[now].val){
        del(tzy[now].l,val);
    }
    else {
        del(tzy[now].r,val);
    }
}
int getrank(int val){
    int now=root;
    int rank=1;
    while(now){
        if(val<=tzy[now].val){
            now=tzy[now].l;
        }
        else{
            rank+=tzy[now].exist+tzy[tzy[now].l].fact;
            now=tzy[now].r;
        }
    }
    return rank;
}
int getnum(int rank){
    int now=root;
    while(now){
        if(tzy[now].exist&&tzy[tzy[now].l].fact+tzy[now].exist==rank){
            break;
        }
        else if(tzy[tzy[now].l].fact>=rank){
            now=tzy[now].l;
        }
        else{
            rank-=tzy[tzy[now].l].fact+tzy[now].exist;
            now=tzy[now].r;
        }
    }
    return tzy[now].val;
}
signed main(){
    int t;
    int n,last=0;
    read(n);
    int ans=0,a; 
    read(t);
    for(int i=1;i<=n;i++){
        read(a);
        ins(root,a);
    }
    int x;
    while(t--){
        int opt,xl;
        read(opt);
        read(xl);
        x=xl^last;
        if(opt==1){
            ins(root,x);
        }
        else if(opt==2){
            del(root,x);
        }
        else if(opt==3){
            last=getrank(x);
        }
        else if(opt==4){
            last=getnum(x);
        }
        else if(opt==5){
            last=getnum(getrank(x)-1);
        }
        else if(opt==6){
            last=getnum(getrank(x+1));
        }
        if(opt==3||opt==4||opt==5||opt==6){
            ans^=last;
        }
    }
    cout<<ans<<endl;
    return 0;
}