[AH2017/HNOI2017]单旋

桃扇骨 2023-10-11 11:16 51阅读 0赞

[题目][Link 1]

\\(\\rm splay\\)水平太差，于是得手玩一下才能发现规律

首先插入一个数，其肯定会成为其**前驱的右儿子或者是后继的左儿子**，进一步手玩发现前驱的右儿子或者是后继的左儿子一定只有一个是空的，我们找到这个空位置插入就好了

于是我们需要一个\\(\\rm std::set\\)来查找前驱后继，同时我们还需要维护每个点的左右儿子和父亲

继续手玩发现由于只有对最大值和最小值的操作，所以对\\(\\rm splay\\)的结构影响很小，于是这个过程中也能维护每个节点的父亲的左右儿子

深度看起来不能用几个数组来维护了，于是我们直接用lct维护这棵树的形态，深度查一下到当前根的路径上的节点个数即可

代码

#include<bits/stdc++.h>
    #define re register
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int maxn=1e5+5;
    struct LinkCutTree {
        int fa[maxn],ch[maxn][2],sz[maxn],rev[maxn];
        int st[maxn],top;
        inline int nrt(int x) {return ch[fa[x]][1]==x||ch[fa[x]][0]==x;}
        inline void pushup(int x) {sz[x]=sz[ch[x][0]]+1+sz[ch[x][1]];}
        inline void rotate(int x) {
            int y=fa[x],z=fa[y],w=ch[y][1]==x,k=ch[x][w^1];
            if(nrt(y)) ch[z][ch[z][1]==y]=x;
            ch[x][w^1]=y,ch[y][w]=k;
            pushup(y),pushup(x);fa[k]=y,fa[y]=x,fa[x]=z;
        }
        inline void work(int x) {rev[x]^=1;std::swap(ch[x][0],ch[x][1]);}
        inline void pushdown(int x) {
            if(!rev[x]) return;rev[x]=0;
            if(ch[x][0]) work(ch[x][0]);
            if(ch[x][1]) work(ch[x][1]);
        }
        inline void splay(int x) {
            int y=x;top=0;
            st[++top]=x;
            while(nrt(y)) y=fa[y],st[++top]=y;
            while(top) pushdown(st[top--]);
            while(nrt(x)) {
                int y=fa[x];
                if(nrt(y)) rotate((ch[y][1]==x)^(ch[fa[y]][1]==y)?x:y);
                rotate(x);
            }
        }
        inline void access(int x) {
            for(re int y=0;x;y=x,x=fa[x])
                splay(x),ch[x][1]=y,pushup(x);
        }
        inline void mrt(int x) {
            access(x);splay(x);work(x);
        }
        inline void link(int x,int y) {
            mrt(x);fa[x]=y;
        }
        inline void split(int x,int y) {
            mrt(x),access(y),splay(y);
        }
        inline void cut(int x,int y) {
            split(x,y);fa[x]=ch[y][0]=0;pushup(y);
        }
        inline int dis(int x,int y) {
            split(x,y);return sz[y];
        }
    }lct;
    struct RBT {
        std::set<int> s;
        #define It std::set<int>::iterator
        inline int pre(int x) {
            It it=s.find(x);
            if(it==s.begin()) return 0;
            --it;return *it;
        }
        inline int nxt(int x) {
            It it=s.find(x);++it;
            if(it==s.end()) return 0;
            return *it;
        }
        inline void del(int x) {s.erase(x);}
        inline void ins(int x) {s.insert(x);}
        inline int Gmin() {It it=s.begin();return *it;}
        inline int Gmax() {It it=s.end();--it;return *it;}
        inline int empty() {return s.empty();}
    }s;
    int n,m,rt;
    int a[maxn],b[maxn],son[maxn][2],op[maxn],fa[maxn];
    inline int find(int x) {
        int l=1,r=n;
        while(l<=r) {
            int mid=l+r>>1;
            if(b[mid]==x) return mid;
            if(b[mid]<x) l=mid+1;else r=mid-1;
        }
        return 0;
    }
    inline int ins(int x) {
        s.ins(x);
        if(!rt) {fa[x]=0;rt=x;return 1;}
        int Pre=s.pre(x);
        if(Pre&&!son[Pre][1]) 
            lct.link(Pre,x),son[Pre][1]=x,fa[x]=Pre;
        else {
            int Nxt=s.nxt(x);
            if(Nxt&&!son[Nxt][0]) 
                lct.link(Nxt,x),son[Nxt][0]=x,fa[x]=Nxt;
        }
        return lct.dis(rt,x);
    }
    inline void move_min() {
        int x=s.Gmin();
        printf("%d\n",lct.dis(x,rt));
        if(x==rt) return;
        lct.cut(fa[x],x);
        if(son[x][1]) lct.cut(x,son[x][1]);
        lct.link(x,rt);
        if(son[x][1]) lct.link(fa[x],son[x][1]);
        fa[son[x][1]]=fa[x];fa[rt]=x;
        son[fa[x]][0]=son[x][1];
        son[x][1]=rt;fa[x]=0;rt=x;
    }
    inline void move_max() {
        int x=s.Gmax();
        printf("%d\n",lct.dis(x,rt));
        if(x==rt) return;
        lct.cut(fa[x],x);
        if(son[x][0]) lct.cut(x,son[x][0]);
        lct.link(rt,x);
        if(son[x][0]) lct.link(fa[x],son[x][0]);
        fa[son[x][0]]=fa[x],fa[rt]=x;
        son[fa[x]][1]=son[x][0];
        son[x][0]=rt,fa[x]=0;rt=x;
    }
    inline void pop(int x) {
        if(son[x][0]) lct.cut(x,son[x][0]),rt=son[x][0];
        if(son[x][1]) lct.cut(x,son[x][1]),rt=son[x][1];
        son[x][0]=son[x][1]=fa[x]=0;
        s.del(x);if(s.empty()) rt=0;
    }
    int main() {
        m=read();
        for(re int i=1;i<=m;i++) {
            op[i]=read();
            if(op[i]==1) a[i]=read(),b[++n]=a[i];
        }
        std::sort(b+1,b+n+1);
        for(re int i=1;i<=m;i++) {
            if(op[i]==1) printf("%d\n",ins(find(a[i])));
            if(op[i]==2) move_min();
            if(op[i]==3) move_max(); 
            if(op[i]==4) move_min(),pop(rt);
            if(op[i]==5) move_max(),pop(rt);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11492087.html

[Link 1]: https://www.luogu.org/problem/P3721