洛谷P3369 普通平衡树(Splay)

àì夳堔傛蜴生んèń 2022-05-14 08:52 165阅读 0赞

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

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

## 分析：这题是平衡树操作的裸题，用treap或者splay都行，我这里用的是splay。splay入门推荐[https://blog.csdn.net/clove\_unique/article/details/50630280][https_blog.csdn.net_clove_unique_article_details_50630280]，写的非常详细。不知道为啥find的时候一定要翻转，不翻转就会wa，欢迎大佬留言指教。 ##

## 代码： ##

#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}};
    
    int ch[N][2],f[N],size[N],cnt[N],key[N];
    int sz,root;
    
    void clear(int x) {///清空节点
        ch[x][0]=ch[x][1]=f[x]=size[x]=cnt[x]=key[x]=0;
    }
    
    bool get(int x) {///判断左右儿子
        return ch[f[x]][1]==x;
    }
    
    void update(int x) {///更新包括x的子树大小
        if(x) {
            size[x]=cnt[x];
            if(ch[x][0]) size[x]+=size[ch[x][0]];
            if(ch[x][1]) size[x]+=size[ch[x][1]];
        }
    }
    
    void rotate(int x) {///旋转
        int old=f[x],oldf=f[old],whichx=get(x);///找到父亲和祖先 判断左右儿子
        ch[old][whichx]=ch[x][whichx^1]; f[ch[old][whichx]]=old;///三步走之一
        ch[x][whichx^1]=old;f[old]=x;///三步走之二
        f[x]=oldf;///三步走之三
        if(oldf) ch[oldf][ch[oldf][1]==old]=x;
        update(old); update(x);
    }
    
    void splay(int x) {///伸展 即多次旋转 直到根
        for(int fa;fa=f[x];rotate(x))
            if(f[fa]&&(get(x)==get(fa))) rotate(fa);///如果儿子 父亲 祖父一条线 先旋转父亲，否则会形成单旋使平衡树失衡
        root=x;
    }
    
    void insert(int x) {///插入x
        if(root==0) { sz++; ch[sz][0]=ch[sz][1]=f[sz]=0; root=sz; size[sz]=cnt[sz]=1; key[sz]=x; return; }///空树特判
        int now=root,fa=0;
        while(1) {
            if(x==key[now]) {///结点的关键字等于当前要插入的点
                cnt[now]++;///now结点的关键字出现的次数(权值)+1
                update(now);///更新当前节点的子树节点个数
                update(fa);///更新父亲节点的子树节点个数
                splay(now);///伸展 把now改为root
                break;
            }
            fa=now;///向下查找左右子树
            now=ch[now][key[now]<x];
            if(now==0) {///如果已经到了最底下了，那么就可以直接插入
                sz++;///更新相关信息
                ch[sz][0]=ch[sz][1]=0;
                f[sz]=fa;
                size[sz]=cnt[sz]=1;
                ch[fa][key[fa]<x]=sz;
                key[sz]=x;
                update(fa);
                splay(sz);
                break;
            }
        }
    }
    
    int find(int x) {///查询x的排名
        int now=root,ans=0;
        while(1) {
            if(x<key[now]) now=ch[now][0];///如果x比当前结点小，即应该向左子树寻找，ans不用改变
            else {
                ans += (ch[now][0]?size[ch[now][0]]:0);///如果x比当前结点大，即应该向右子树寻找，ans需要加上左子树的大小以及根的大小
                if(x==key[now]) {///不要忘记了再splay一下
                    splay(now); return ans+1;
                }
                ans += cnt[now];
                now = ch[now][1];
            }
        }
    }
    
    int findx(int x) {///找到排名为x的点
        int now=root;
        while(1) {
            if(ch[now][0]&&x<=size[ch[now][0]]) now=ch[now][0];///如果当前点有左子树，并且x比左子树的大小小的话，即向左子树寻找
            else {
                ///否则，向右子树寻找：先判断是否有右子树，然后记录右子树的大小以及当前点的大小（都为权值），
                ///用于判断是否需要继续向右子树寻找。
                int temp=(ch[now][0]?size[ch[now][0]]:0)+cnt[now];
                if(x<=temp) return key[now];
                x-=temp; now = ch[now][1];
            }
        }
    }
    
    int pre() {///求x的前驱 前驱定义为小于x，且最大的数
        int now=ch[root][0];///求x的前驱其实就是求x的左子树的最右边的一个结点
        while(ch[now][1]) now=ch[now][1];
        return now;
    }
    
    int next() {///求x的后继 后继定义为大于x，且最小的数
        int now=ch[root][1];///后继是求x的右子树的左边一个结点
        while(ch[now][0]) now=ch[now][0];
        return now;
    }
    
    void del(int x) {///删除操作
        int whatever=find(x);///随便find一下x。目的是：将x旋转到根。
        if(cnt[root]>1) { cnt[root]--; update(root); return; }///如果cnt[root]>1，即不只有一个x的话，直接-1返回。
        if(!ch[root][0]&&!ch[root][1]) { clear(root); root=0; return; }///如果root并没有孩子，就说名树上只有一个x而已，直接clear返回。
        if(!ch[root][0]) {///如果root只有右儿子，那么直接clear root，然后把唯一的儿子当作根就可以了（f赋0，root赋为唯一的儿子）
            int oldroot=root; root=ch[root][1]; f[root]=0; clear(oldroot); return;
        }else if(!ch[root][1]) {///如果root只有左儿子，那么直接clear root，然后把唯一的儿子当作根就可以了（f赋0，root赋为唯一的儿子）
            int oldroot=root; root=ch[root][0]; f[root]=0; clear(oldroot); return;
        }
        int leftbig=pre(),oldroot=root;///我们找到新根，也就是x的前驱（x左子树最大的一个点），将它旋转到根。
        splay(leftbig);
        ch[root][1]=ch[oldroot][1];///然后将原来x的右子树接到新根的右子树上（注意这个操作需要改变父子关系）。这实际上就把x删除了。
        f[ch[oldroot][1]]=root;
        clear(oldroot);///清空原根
        update(root);///不要忘了update新根。
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int n,opt,x;
        cin>>n;
        rep(i,1,n) {
            cin>>opt>>x;
            if(opt==1) insert(x);
            else if(opt==2) del(x);
            else if(opt==3) cout<<find(x)<<endl;
            else if(opt==4) cout<<findx(x)<<endl;
            else if(opt==5) insert(x),cout<<key[pre()]<<endl,del(x);///问题可以转化为将x插入，求出树上的前驱（后继），再将x删除的问题。
            else if(opt==6) insert(x),cout<<key[next()]<<endl,del(x);
        }
        return 0;
    }

[Link 1]: https://www.luogu.org/problemnew/show/P3369
[https_blog.csdn.net_clove_unique_article_details_50630280]: https://blog.csdn.net/clove_unique/article/details/50630280