【数据结构】普通平衡树

来自刚刚学会Treap的蒟蒻

题目链接： - P6136 【模板】普通平衡树（数据加强版） - 弱化版 P6136 【模板】普通平衡树

特别不习惯用一堆数组，结构体多香啊

struct node{
    int son[2];//son[
    int size,cnt;
    int val,rd;
}trp[1500000];
int tot,root;

其实完整代码里都有~ 只不过无聊，单独拿出来~

int rrand(void){
    return seed=(int)((long long)(seed)*974485642LL%21474836LL);
    /*手写rand()取随机数*/
}

#include<bits/stdc++.h>
#define re register
#define rd(x) x=read()
struct node{
    int son[2];//son[0]左儿子，son[1]右儿子
    int size,cnt;
    //因为treap不希望出现值相同的节点，（想想为什么）
    //所以用cnt统计相同的值
    int val,rd;
    //rd 是随机的权值，整个树按照这个打乱
    //当然，rd也可以被称为该节点的优先级
}trp[1500000];
int tot,root;
int seed=5201314;
int rrand(void){
    return seed=(int)((long long)(seed)*974485642LL%21474836LL);
    /*手写rand()取随机数*/
}

void newnode(int &now,int val){
    /*
    val = val
    size = 1
    cnt = 1;
    rd rand()
    */
    /*基础的新建节点，没毛病*/
    now = ++tot;
    trp[now].val = val;
    trp[now].size = trp[now].cnt = 1;
    trp[now].rd = rrand();
    /*这里吐槽下,treap真的是看脸的算法啊*/
}
void update(int now){
    /*更新新节点，很简单，这里没啥问题 */
    trp[now].size = trp[trp[now].son[0]].size+trp[trp[now].son[1]].size+trp[now].cnt;
}
void rotate(int &now,int d){
    /*
    自闭了十分钟的旋转操作，
    位运算理解成左右儿子切换或者左右方向切换就好。
    */
    int son = trp[now].son[d^1];
    trp[now].son[d^1] = trp[son].son[d];
    trp[son].son[d] = now;
    now = son;
    /*注意，从下到上更新，先更新旋转后节点的d儿子，最后更新旋转的now节点*/
    update(trp[now].son[d]);
    update(now);
}
void insert(int &now,int val){
    if(!now){
        newnode(now,val);//终于可以插入新节点了
        return;
    }//在那之前，我们需要找到在何处插
    ++trp[now].size;
    if(trp[now].val==val){
        trp[now].cnt++;//前面提到的计数器，相同的值直接统计数量就好
        update(now);//我还在思考这里要不要update一下
        return;
    }
    if(trp[now].val>val){
        insert(trp[now].son[0],val);
        if(trp[now].rd<trp[trp[now].son[0]].rd)
            rotate(now,1);
    }//左右分头，记住一点，这棵树中，越往上rd越大，所以我们if比较里的内容其实很简单
    //如果遇到儿子的rd比父辈大的时候，我们就旋转一下
    else{
        insert(trp[now].son[1],val);
        if(trp[now].rd<trp[trp[now].son[1]].rd)
            rotate(now,0);
    }
    update(now);
}
void del(int &now,int val){
    if(!now)return;//都没节点了，你删个锤子，可以加返回值判断是否删成功
    ++trp[now].size;
    if(trp[now].val==val){
        if(trp[now].cnt>1){
            trp[now].cnt--;
            update(now);
            return;
        }
        if(trp[now].son[0]||trp[now].son[1]){
            if(!trp[now].son[1]||trp[trp[now].son[0]].rd>trp[trp[now].son[1]].rd)
                rotate(now,1),del(trp[now].son[1],val);
            else
                rotate(now,0),del(trp[now].son[0],val);
        }//删除这段其实用手画三四张模拟就懂了
        else now = 0;
    }//蒟蒻的我可能会在B站录个视频什么的
    else if(trp[now].val>val)
        del(trp[now].son[0],val);
    else del(trp[now].son[1],val);
    update(now);
}
int find_rank(int now,int val){ //找到val的排名
    if(!now)
        return INT_MIN;
    if(trp[now].val==val)
        return trp[trp[now].son[0]].size+1;
    else if(trp[now].val>val)
        return find_rank(trp[now].son[0],val);
    else
        return trp[trp[now].son[0]].size + trp[now].cnt + find_rank(trp[now].son[1],val);
}
int find_val(int now,int rank){ //找到排名为rank的值
    if(!now)
        return INT_MAX;
    if(trp[trp[now].son[0]].size>=rank)
        return find_val(trp[now].son[0],rank);
    else if(trp[trp[now].son[0]].size+trp[now].cnt>=rank)
        return trp[now].val;
    else
        return find_val(trp[now].son[1],rank-trp[trp[now].son[0]].size-trp[now].cnt);
}
int find_pre(int val){ //找到val的前驱
    re int now = root,pre = 0;
    while(now){
        if(trp[now].val<val)
            pre = trp[now].val,now = trp[now].son[1];
        else
            now = trp[now].son[0];
    }
    return pre;
}
int find_nex(int val){  //找到val的后继
    re int now = root,nex = 0;
    while(now){
        if(trp[now].val>val)
            nex = trp[now].val,now = trp[now].son[0];
        else
            now = trp[now].son[1];
    }
    return nex;
}
inline int read(){ //读入优化
    re int ans = 0;
    re bool f = 1;
    re char ch = getchar();
    while(ch<'0'||ch>'9')ch=='-'?f=0,ch=getchar():ch=getchar();
    while(ch>='0'&&ch<='9')ans =(ans<<3)+(ans<<1)+(ch^48),ch = getchar(); 
    return f?ans:-ans;
} 
signed main(void){
    int n,m,last = 0,ans = 0,ooo;
    n = read();m = read();++n;++m;
    while(--n){
        ooo = read();
        insert(root,ooo);
    }
    while(--m){
        int opt,x;
        opt = read();
        x = read();
        switch(opt){ //这里就是一个简单的switch语句，我就不多说了
            case 1:
                insert(root,x^last);
                break;
            case 2:
                del(root,x^last);
                break;
            case 3:
                ans ^= (last = find_rank(root,x^last));
                break;
            case 4:
                ans ^= (last = find_val(root,x^last));
                break;
            case 5:
                ans ^= (last = find_pre(x^last));
                break;
            case 6:
                ans ^= (last = find_nex(x^last));
                break;
        }
    }
    printf("%d",ans);
    return 0;
}

感谢观看，如有不懂欢迎评论，博主全年365天无休，24小时内必回

嘿嘿，点个关注推荐呗 ~