模板Treap56pts悬2关求条

#include<cstdio>
#include<random>
#include<ctime>
using namespace std;
#define ls(u) tr[u].lson
#define rs(u) tr[u].rson
const int MAXN=1.1e6+10;
const int INF=2147483647;
struct NODE{
    int lson,rson;
    int val;
    int dat;
    int cnt;
    int size_subtree;
    NODE(){
        lson=0,rson=0;
    }
}tr[MAXN];
int tot=0,root=1;
int n,Q,a;
int New(int val){
    ++tot;
    tr[tot].val=val;
    tr[tot].dat=rand();
    tr[tot].cnt=1;
    tr[tot].size_subtree=1;
    return tot;
}
void pushup(int u){
    tr[u].size_subtree=tr[ls(u)].size_subtree+tr[rs(u)].size_subtree+tr[u].cnt;
}
void zig(int &u){
    int q=ls(u);
    ls(u)=rs(q);rs(q)=u;
    u=q;
    pushup(rs(u));
    pushup(u);
}
void zag(int &u){
    int q=rs(u);
    rs(u)=ls(q);ls(q)=u;
    u=q;
    pushup(ls(u));
    pushup(u);
}
void Insert(int &u,int val){
    if(u==0){
        u=New(val);
        pushup(u);
        return;
    }
    if(val==tr[u].val){
        ++tr[u].cnt;
        pushup(u);
        return;
    }
    if(val<tr[u].val){
        Insert(ls(u),val);
        if(tr[u].dat<tr[ls(u)].dat){
            zig(u);
        }
    }
    else{
        Insert(rs(u),val);
        if(tr[u].dat<tr[rs(u)].dat){
            zag(u);
        }
    }
    pushup(u);
}
void Delete(int &u,int val){//在根结点为u的子树里找到val并删除
    if(u==0){
        return;
    }
    if(val==tr[u].val){
        if(tr[u].cnt>1){
            --tr[u].cnt;
            pushup(u);
            return;
        }
        if(ls(u)||rs(u)){
            if(rs(u)==0||tr[ls(u)].dat>tr[rs(u)].dat){
                zig(u);
                Delete(rs(u),val);
            }
            else{
                zag(u);
                Delete(ls(u),val);
            }
            pushup(u);
        }
        else{
            u=0;
        }
        return;
    }
    if(val<tr[u].val){
        Delete(ls(u),val);
    }
    else{
        Delete(rs(u),val);
    }
    pushup(u);
    return;
}
int get_next(int val){
    int u=root;
    int ans=3;
    while(u){
        if(val==tr[u].val){
            if(rs(u)){
                u=rs(u);
                while(ls(u)){
                    u=ls(u);
                }
                ans=u;
            }
            break;
        }
        if(val<tr[u].val&&tr[u].val<tr[ans].val){
            ans=u;
        }
        u=val<tr[u].val?ls(u):rs(u);
    }
    return tr[ans].val;
}
int get_prev(int val){
    int u=root;
    int ans=2;
    while(u){
        if(val==tr[u].val){
            if(ls(u)){
                u=ls(u);
                while(rs(u)){
                    u=rs(u);
                }
                ans=u;
            }
            break;
        }
        if(val>tr[u].val&&tr[u].val>tr[ans].val){
            ans=u;
        }
        u=val<tr[u].val?ls(u):rs(u);
    }
    return tr[ans].val;
}
int get_rank(int val){
    int rk=0,u=root;
    while(u){
        if(val==tr[u].val){
            break;
        }
        if(val<tr[u].val){
            u=ls(u);
        }
        else{
            rk+=(tr[u].size_subtree-tr[rs(u)].size_subtree);
            u=rs(u);
        }
    }
    return rk-1;
}
int get_value(int rk){
    int u=root;
    ++rk;++rk;
    while(u){
        if(tr[ls(u)].size_subtree==rk-1){
            return tr[u].val;
        }
        if(tr[u].cnt+tr[ls(u)].size_subtree<rk){
            rk-=tr[u].cnt+tr[ls(u)].size_subtree;
            u=rs(u);
        }
        else{
            u=ls(u);
        }
    }
    return -1;
}
void build(){
    New(-1);
    Insert(root,-INF);
    Insert(root,INF);
}
int main(){
    freopen("P6136.in","r",stdin);
    srand(time(0));
    build();
    scanf("%d%d",&n,&Q);
    for(int i=1;i<=n;++i){
        scanf("%d",&a);
        Insert(root,a);
    }
    int op,x;
    int lst_ans=0;
    int XOR_ANS=0;
    while(Q--){
        scanf("%d%d",&op,&x);
        x^=lst_ans;
        switch(op){
            case 1:{
                Insert(root,x);
                break;
            }
            case 2:{
                Delete(root,x);
                break;
            }
            case 3:{
                lst_ans=get_rank(x);
                break;
            }
            case 4:{
                lst_ans=get_value(x);
                break;
            }
            case 5:{
                lst_ans=get_prev(x);
                break;
            }
            case 6:{
                lst_ans=get_next(x);
                break;
            }
        }
        if(op>=3){
//          printf("%d\n",lst_ans);
            XOR_ANS^=lst_ans;
        }
    }
    printf("%d",XOR_ANS);
    fclose(stdin);
    return 0;
}

这是提交记录