P3369 【模板】普通平衡树（treap）

系统管理员 2022-05-14 09:17 135阅读 0赞

## 题目：[点击打开链接][Link 1] ##

## 题意：中文题，不解释。 ##

## 分析：这题是平衡树操作的裸题，用treap或者splay都行，我这里用的是treap。treap入门推荐[https://www.cnblogs.com/MyStringIsNotNull/p/9165675.html][https_www.cnblogs.com_MyStringIsNotNull_p_9165675.html]，写的非常详细，代码参考[https://www.cnblogs.com/candy99/p/6105347.html][https_www.cnblogs.com_candy99_p_6105347.html]。 ##

## 代码： ##

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #pragma comment(linker, "/STACK:102400000,102400000")
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    typedef pair<int,int> PII;
    const ll mod = 1e9+7;
    const int N = 1e6+10;
    
    ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    struct node{
        int l,r,size,v,w,rnd;///左、右子树、包含本节点的子树大小、节点的值、节点值的数量、优先级
    }t[N];
    int cnt,root;///节点个数、根
    inline void update(int x){t[x].size=t[t[x].l].size+t[t[x].r].size+t[x].w;}///更新节点的子树个数
    inline void rturn(int &x){///左旋
        int c=t[x].l;t[x].l=t[c].r;t[c].r=x;
        t[c].size=t[x].size;update(x);x=c;
    }
    inline void lturn(int &x){///右旋
        int c=t[x].r;t[x].r=t[c].l;t[c].l=x;
        t[c].size=t[x].size;update(x);x=c;
    }
    void insert(int &x,int v){///插入
        if(x==0){///空树
            cnt++;x=cnt;
            t[cnt].l=t[cnt].r=0;
            t[cnt].v=v;t[cnt].w=t[cnt].size=1;t[cnt].rnd=rand();
            return;
        }
        t[x].size++;///子树节点个数+1
        if(t[x].v==v) t[x].w++;///节点值次数+1
        else if(v<t[x].v){
            insert(t[x].l,v);/// 递归左子树
            if(t[t[x].l].rnd<t[x].rnd) rturn(x);///插入后作出调整(右旋)
        }else{
            insert(t[x].r,v);/// 递归右子树
            if(t[t[x].r].rnd<t[x].rnd) lturn(x);///插入后作出调整(左旋)
        }
    }
    void del(int &x,int v){///删除值为x的数(若有多个相同的数，因只删除一个)
        if(x==0) return;///空树 直接返回
        if(t[x].v==v){
            if(t[x].w>1){t[x].w--;t[x].size--;return;}///次数>1 次数-1 返回
            if(t[x].l*t[x].r==0) x=t[x].l+t[x].r;///一个孩子为空，直接用另一个代替
            else if(t[t[x].l].rnd<t[t[x].r].rnd)
                rturn(x),del(x,v); ///右旋再继续找
            else lturn(x),del(x,v);///左旋再继续找
        }else {
            t[x].size--;///节点值次数-1
            if(v<t[x].v) del(t[x].l,v);///找左子树
            else del(t[x].r,v);///找右子树
        }
    }
    int rnk(int x,int v){///查找数v的排名
        if(x==0) return 0;///空树 返回0
        if(t[x].v==v) return t[t[x].l].size+1;///找到 返回
        else if(v<t[x].v) return rnk(t[x].l,v);///继续找左子树
        else return t[t[x].l].size+t[x].w+rnk(t[x].r,v);///+左子树节点个数后 继续找左子树
    }
    int kth(int x,int k){///查找排名为k的数
        if(x==0) return 0;///空树 返回0
        if(k<=t[t[x].l].size) return kth(t[x].l,k);///左子树节点个数大于k 继续往左子树找
        else if(k>t[t[x].l].size+t[x].w)
            return kth(t[x].r,k-t[t[x].l].size-t[x].w);///左子树节点个数小于k 继续往右子树找
        else return t[x].v;///找到 返回
    }
    int ans;
    void pre(int x,int v){///查找v的前驱
        if(x==0) return;
        if(v>t[x].v) ans=x,pre(t[x].r,v);///找到小于v的节点 往右子树找
        else pre(t[x].l,v);///否则往左子树找
    }
    void suf(int x,int v){///查找v的后继
        if(x==0) return;
        if(v<t[x].v) ans=x,suf(t[x].l,v);///找到大于v的节点 往左子树找
        else suf(t[x].r,v);///否则往右子树找
    }
    int n,op,x;
    int main(){
        srand(222);///随机数种子
        cin>>n;
        while(n--){
            cin>>op>>x;
            if(op==1) insert(root,x);
            else if(op==2) del(root,x);
            else if(op==3) cout<<rnk(root,x)<<endl;
            else if(op==4) cout<<kth(root,x)<<endl;
            else if(op==5) ans=0,pre(root,x),cout<<t[ans].v<<endl;
            else if(op==6) ans=0,suf(root,x),cout<<t[ans].v<<endl;
        }
        return 0;
    }

[Link 1]: https://www.luogu.org/problemnew/show/P3369
[https_www.cnblogs.com_MyStringIsNotNull_p_9165675.html]: https://www.cnblogs.com/MyStringIsNotNull/p/9165675.html
[https_www.cnblogs.com_candy99_p_6105347.html]: https://www.cnblogs.com/candy99/p/6105347.html