! AHOI/HNOI2017单旋

\(m1e5\)

套路：题目是splay，就显然不是spaly

单旋与双旋的区别：

若为一条链，单旋完了还是链，复杂度不对

双旋我们判断了如果与父亲及祖先在一条直线上则先转祖先，则不会发生这种情况

SOL：

发现其实树的形态变化并不大

例如将最小值旋至根：

1. 把最小值的儿子当做其父亲的对应儿子
2. 让最小值做根节点

深度变化：除最小值子树+1，即所有>=最小值父亲的值

删除根节点则所有点-1

考虑插入：

插入值的前驱后继一定是连在一起的

插入值只可能做前驱或后继的儿子，于是直接选深度最大的即可

离散化+树状数组+set即可解决

时间复杂度\(O(nlog_n)\)

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f==1?x:-x;
}
const int N=1e5+4;
int m,cn,op[N],uu[N],b[N],rt,ch[N][2],fa[N],t[N];
set<int>s;
inline void add(int x,int v){
    for(;x<=cn;x+=x&-x)t[x]+=v;
}
inline int ask(int x){
    int ret=0;
    for(;x;x-=x&-x)ret+=t[x];
    return ret;
}
int main(){
    m=read();
    for(int i=1;i<=m;i++){
        op[i]=read();
        if(op[i]==1)uu[i]=b[++cn]=read();
    }
    sort(b+1,b+cn+1);
    cn=unique(b+1,b+cn+1)-b-1;
    for(int i=1,u,x,v;i<=m;i++){
        if(op[i]==1){
            u=lower_bound(b+1,b+cn+1,uu[i])-b;
            set<int>::iterator it=s.lower_bound(u);
            if(it!=s.end()&&!ch[*it][0]){
                ch[*it][0]=u;
                fa[u]=*it;
                add(u,x=ask(*it)+1-ask(u));
                add(u+1,-x);
            }
            else if(it!=s.begin()&&!ch[*(--it)][1]){
                ch[*it][1]=u;
                fa[u]=*it;
                add(u,x=ask(*it)+1-ask(u));
                add(u+1,-x);
            }
            else{
                rt=u;
                add(u,x=1-ask(u));
                add(u+1,-x);
            }
            s.insert(u);
            cout<<ask(u)<<"\n";
        }
        else if(op[i]==2){
            u=*s.begin();
            cout<<ask(u)<<"\n";
            v=fa[u];
            if(v){
                add(v,1);
                fa[ch[u][1]]=v;
                ch[v][0]=ch[u][1];
                add(u,x=1-ask(u));
                add(u+1,-x);
                ch[u][1]=rt;
                fa[rt]=u;
                fa[u]=0;
                rt=u;
            }
        }
        else if(op[i]==3){
            u=*s.rbegin();
            cout<<ask(u)<<"\n";
            v=fa[u];
            if(v){
                add(1,1);add(v+1,-1);
                fa[ch[u][0]]=v;
                ch[v][1]=ch[u][0];
                add(u,x=1-ask(u));
                add(u+1,-x);
                ch[u][0]=rt;
                fa[rt]=u;
                fa[u]=0;
                rt=u;
            }
        }
        else if(op[i]==4){
            u=*s.begin();
            cout<<ask(u)<<"\n";
            v=fa[u];
            if(v){
                add(v,1);
                fa[ch[u][1]]=v;
                ch[v][0]=ch[u][1];
                add(u,x=1-ask(u));
                add(u+1,-x);
                ch[u][1]=rt;
                fa[rt]=u;
                fa[u]=0;
                rt=u;
            }
            fa[rt=ch[u][1]]=0;
            add(1,-1);
            s.erase(u);
        }
        else{
            u=*s.rbegin();
            cout<<ask(u)<<"\n";
            v=fa[u];
            if(v){
                add(1,1);add(v+1,-1);
                fa[ch[u][0]]=v;
                ch[v][1]=ch[u][0];
                add(u,x=1-ask(u));
                add(u+1,-x);
                ch[u][0]=rt;
                fa[rt]=u;
                fa[u]=0;
                rt=u;
            }
            fa[rt=ch[u][0]]=0;
            add(1,-1);
            s.erase(u);
        }
    }
    return (0-0);
}

! AHOI/HNOI2017单旋

原文：https://www.cnblogs.com/aurora2004/p/12519495.html