splay

splay与他的解析

二叉搜索树

我们搞一棵树，保证左子树所有点的权值比父亲小，右子树所有点权值比父亲大

显然这个玩意可以快速查询一个数存不存在，排名啦啥的

插入的时候直接顺序造节点，删除的时候，断开重连是件很愚蠢的事情

应该把删除节点和他右子树最左边那个或者左子树最右边那个交换，销毁它

这样有什么问题呢？

如果坑逼出题人给你搞成了链，直接起飞成$ O(n)$了

这不就挂了

那么该怎么搞呢

伸展树splay出现了

splay，旋转，自我调整，

旋转

本图片引用自liuzhangfeiabc课件

我们可以看到，转x，就是让f变成x的右儿子，x的右儿子变成f的左儿子，x的右儿子变成f，x代替f

void ro(int x){
    int f=po[x].fa;
    int gf=po[f].fa;
    int xp=ident(x);
    int fp=ident(f);
    connect(po[x].son[xp^1],f,xp);
    connect(f,x,xp^1);
    connect(x,gf,fp);
    update(f);
    update(x);
}

但是出题人还能接着卡你

怎么办呢,我们一次转俩，直接强行链改树

splay

void splay(int x,int to){
    to=po[to].fa;
    while(po[x].fa!=to){
        int f=po[x].fa;
        if(po[f].fa==to) ro(x);
        else if(ident(x)==ident(f)) ro(f),ro(x);
        else ro(x),ro(x);
    }
}.

这又是在干什么呢

我们可以把一个节点移到你想去的任何位置如果爹，爹的爹和儿子共线，就要先转爹，不然就转两次儿子，就可以成功的压成树了

更具体的操作

插入 这里没什么大坑，就是记得最后splay一下

void insert(int x){
    int now=po[0].son[1];
    if(now==0){
        creat(x,0);
        po[0].son[1]=tot;
    }else{
        while(1){
            po[now].sum++;
            if(po[now].val==x){
                po[now].cnt++;
                splay(now,po[0].son[1]);
                return ;
            }
            int nex=x<po[now].val?0:1;
            if(!po[now].son[nex]){
                int p=creat(x,now);
                po[now].son[nex]=p;
                splay(p,po[0].son[1]);
                return ;
            }
            now=po[now].son[nex];
        }
    }
}

寻找排名

也很好理解，记得splay

int find(int x){
    int now=po[0].son[1];
    while(1){
        if(!now) return 0;
        if(po[now].val==x) {
            splay(now,po[0].son[1]);
            return now;
        }
        int nex=x<po[now].val?0:1;
        now=po[now].son[nex];
    }
}

删除

还是很好解决的，先找到它，如果它是叶子，直接删掉，如果它没有左儿子的，就直接把右儿子接上去，如果都有，就找它右子树最左的那个，splay进行交换，销毁

void del(int x){
    int pos=find(x);
    if(!pos) return ;
    if(po[pos].cnt>1){
        po[pos].cnt--;
        po[pos].sum--;
        return ;
    }else{
        if(!po[pos].son[0]&&!po[pos].son[1]) {
            po[0].son[1]=0;
            return ;
        }else if(!po[pos].son[0]){
            po[0].son[1]=po[pos].son[1];
            po[po[0].son[1]].fa=0;
            return ;
        } else{
            int le=po[pos].son[0];
            while(po[le].son[1]) le=po[le].son[1];
            splay(le,po[pos].son[0]);
            connect(po[pos].son[1],le,1);
            connect(le,0,1);
            update(le);
        }
    }
}

按照排名找数

同理

找前缀

记得一直取max

后缀

和前缀反着

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstring>
#define int long long
using namespace std;
const int maxn=1e6+10;
const int mod=10007;
const int inf=1e9+10;
struct p{
    int fa;
    int son[2];
    int val;
    int cnt;
    int sum;
}po[maxn];
int tot;
int n,opt;int x;
int ps;
inline int read(){
    int res=0,k=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')k=-1;
        c=getchar();
    }
    while(isdigit(c)){
        res=(res<<1)+(res<<3)+c-48;
        c=getchar();
    }
    return res*k;
}
void update(int x){
    po[x].sum=po[po[x].son[0]].sum+po[po[x].son[1]].sum+po[x].cnt;
}
int ident(int x){
    return po[po[x].fa].son[0]==x?0:1;
}
void connect(int x,int fa,int s){
    po[fa].son[s]=x;
    po[x].fa=fa;
}
void ro(int x){
    int f=po[x].fa;
    int gf=po[f].fa;
    int xp=ident(x);
    int fp=ident(f);
    connect(po[x].son[xp^1],f,xp);
    connect(f,x,xp^1);
    connect(x,gf,fp);
    update(f);
    update(x);
}
void splay(int x,int to){
    to=po[to].fa;
    while(po[x].fa!=to){
        int f=po[x].fa;
        if(po[f].fa==to) ro(x);
        else if(ident(x)==ident(f)) ro(f),ro(x);
        else ro(x),ro(x);
    }
}
int creat(int val,int f){
    ++tot;
    po[tot].fa=f;
    po[tot].sum=po[tot].cnt=1;
    po[tot].val=val;
    return tot;
}
void insert(int x){
    int now=po[0].son[1];
    if(now==0){
        creat(x,0);
        po[0].son[1]=tot;
    }else{
        while(1){
            po[now].sum++;
            if(po[now].val==x){
                po[now].cnt++;
                splay(now,po[0].son[1]);
                return ;
            }
            int nex=x<po[now].val?0:1;
            if(!po[now].son[nex]){
                int p=creat(x,now);
                po[now].son[nex]=p;
                splay(p,po[0].son[1]);
                return ;
            }
            now=po[now].son[nex];
        }
    }
}
int find(int x){
    int now=po[0].son[1];
    while(1){
        if(!now) return 0;
        if(po[now].val==x) {
            splay(now,po[0].son[1]);
            return now;
        }
        int nex=x<po[now].val?0:1;
        now=po[now].son[nex];
    }
}
void del(int x){
    int pos=find(x);
    if(!pos) return ;
    if(po[pos].cnt>1){
        po[pos].cnt--;
        po[pos].sum--;
        return ;
    }else{
        if(!po[pos].son[0]&&!po[pos].son[1]) {
            po[0].son[1]=0;
            return ;
        }else if(!po[pos].son[0]){
            po[0].son[1]=po[pos].son[1];
            po[po[0].son[1]].fa=0;
            return ;
        } else{
            int le=po[pos].son[0];
            while(po[le].son[1]) le=po[le].son[1];
            splay(le,po[pos].son[0]);
            connect(po[pos].son[1],le,1);
            connect(le,0,1);
            update(le);
        }
    }
}
int rak(int x){
    int now=po[0].son[1];
    int ans=0;
    while(1){
        if(po[now].val==x) {
    //  splay(now,po[0].son[1]);
         ans+=po[po[now].son[0]].sum+1;
         splay(now,po[0].son[1]);;
         return ans;
        }
        int nex=x<po[now].val?0:1;
        if(nex==1) ans =ans+po[po[now].son[0]].sum+po[now].cnt;
        now=po[now].son[nex];
    }
}
int kth(int x){
    int now=po[0].son[1];
    while(1){
        int re=po[now].sum-po[po[now].son[1]].sum;
        if(po[po[now].son[0]].sum<x&&x<=re){
            return po[now].val;
        }
        if(x<re) now=po[now].son[0];
        else now =po[now].son[1],x-=re;
    }
}
int lower(int x){
    int now=po[0].son[1];
    int ans=-inf;
    while(now){
        if(po[now].val<x) ans=max(ans,po[now].val);
        int nex=x<=po[now].val?0:1;//等于也要往左走 
        now=po[now].son[nex];
    }
    return ans;
}
int upper(int x){
    int now=po[0].son[1];
    int ans=inf;
    while(now){
        if(po[now].val>x) ans=min(ans,po[now].val);
        int nex=x<po[now].val?0:1;
        now=po[now].son[nex];
    }
    return ans;
}
signed main(){
    n=read();
    while(n--){
        opt=read();
        x=read();
        if(opt==1) insert(x);
        else if(opt==2) del(x);
        else if(opt==3) printf("%dn",rak(x));
        else if(opt==4) printf("%dn",kth(x));
        else if(opt==5) printf("%dn",lower(x));
        else if(opt==6) printf("%dn",upper(x));
    }
    return 0;
}