平衡树

由于我们学过数据结构,在二叉搜索树中,如果给出的数据是一条链的话,那么每次查询等操作都是O(n)的级别,所以为了优化搜索查找修改的效率,需要创建平衡树,来达到logn级别的查询和修改

对于一颗二叉搜索树,我们可以将它进行分裂操作,假如我们要进行查询一个数 $u$ 那么我们就可以分裂这棵树,把他分成两颗树,由于二叉树的性质,我们肯定能够把左边的树分成 $<= u$ 右边的树都是 $>u$ 的两颗树有了这两棵树,我们就可以进行查询,由于分裂之后二叉搜索树的性质不变,就可以做到查询操作了,不过由于我们分裂了,所以分裂之后不要忘记合并就是了

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
struct node{
    int l,r,key,sz,val;//左子树,右子树,关键值,树的大小,以及树中存的值
}tr[N];
int t1,t2,t3,ck,root;//t1是分裂之后左子树的根节点,t2是右子树的根节点
//t3是 x=v 的根节点,ck就是一个节点计数器,root是树的根
mt19937 sj(1141514); //随机数,我们将树的尽量分成大根堆的形式,key即为值
//由于正态分布的原因,所以我们创建出来的树可以压到log的高度
int xj(int x){
    tr[++ck]={0,0,(int)sj(),1,x};
    return ck;
}
void pushup(int u){
    tr[u].sz=tr[tr[u].l].sz+tr[tr[u].r].sz+1;
}
void split(int u,int v,int &x,int &y){
    if(!u) return x=y=0,void();
    if(tr[u].val>v) y=u,split(tr[u].l,v,x,tr[u].l);//若节点大于查询值,向左分裂
    else x=u,split(tr[u].r,v,tr[u].r,y);
    pushup(u);
}
int merge(int x,int y){
    if(!x||!y) return x+y;
    if(tr[x].key>tr[y].key){//大根堆性质合并 
        tr[x].r=merge(tr[x].r,y);
        pushup(x);
        return x;
    }
    else{
        tr[y].l=merge(x,tr[y].l);
        pushup(y);
        return y;
    }
}
void insert(int x){
    split(root,x,t1,t2);
    root=merge(merge(t1,xj(x)),t2);
}
void erase(int x){
    split(root,x,t1,t2); //先根据x分成两半
    split(t1,x-1,t1,t3);//在从<=x的树上继续分成两半,此时分成 <=x-1, >x-1
    t3=merge(tr[t3].l,tr[t3].r);//t3即为 >x-1的根节点,所以我们直接合并左右子树即可
    //不加入根节点,因为此时根节点一定是 =x
    root=merge(merge(t1,t3),t2);//怎么分的树怎么合  
}
int find(int x){
    split(root,x-1,t1,t2);
    int res=tr[t1].sz+1;
    root=merge(t1,t2);
    return res;
}
int kth(int x){
    int u=root;
    while(u){
        int tmp=tr[tr[u].l].sz+1; //左子树的值全部比当前节点小
        if(tmp==x) break;
        else if(tmp>x) u=tr[u].l;
        else x-=tmp,u=tr[u].r;  
    }
    return tr[u].val;
}
int find_pre(int x){
    split(root,x-1,t1,t2);
    int u=t1;
    while(tr[u].r) u=tr[u].r;
    root=merge(t1,t2);
    return tr[u].val;
}
int find_next(int x){
    split(root,x,t1,t2);
    int u=t2;
    while(tr[u].l) u=tr[u].l;
    root=merge(t1,t2);
    return tr[u].val;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x; cin>>x;
        insert(x);
    }
    int lst=0,res=0;
    while(m--){
        int op,x; cin>>op>>x;
        x^=lst;
        if(op==1) insert(x);
        else if(op==2) erase(x);
        else if(op==3) lst=find(x),res^=lst;
        else if(op==4) lst=kth(x),res^=lst;
        else if(op==5) lst=find_pre(x),res^=lst;
        else lst=find_next(x),res^=lst;
    }
    cout<<res;
    return 0;
}