splay板子（持续更新）

xuzz · 2023-01-10 11:40:52 · 个人记录

目前已有clear，update，rotate，splay，splay2（指定旋转到谁的儿子），insert，pre，nex，kth，rank，del。

下一步：区间翻转，可持久化。

终极目标：LCT。

初步优化：垃圾回收。

终极优化：内存池。

#include<bits/stdc++.h>
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') f=(ch=='-')?-1:1,ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
const int N=100005;
struct Splay
{
    int ch[N][2],f[N],size[N],cnt[N],ttt,root,zhi[N];
    void clear(int x){ch[x][0]=ch[x][1]=f[x]=zhi[x]=size[x]=cnt[x]=0;}
    inline void update(int x){size[x]=cnt[x]+size[ch[x][0]]+size[ch[x][1]];}
    inline void rotate(int x)
    {
        int y=f[x],z=f[y],k=(ch[f[x]][1]==x);
        ch[y][k]=ch[x][!k];
        if(ch[x][!k]) f[ch[x][!k]]=y;
        ch[x][!k]=y,f[y]=x,f[x]=z;
        if(z) ch[z][ch[z][1]==y]=x;
        update(x),update(y);
        return;
    }
    void splay(int x)
    {
        for(int fa;(fa=f[x]);rotate(x))
            if(f[fa])
                rotate((ch[f[x]][1]==x)==(ch[f[fa]][1]==fa)?fa:x);
        root=x;
    }
    void splay2(int x,int k)
    {
        for(int fa;(fa=f[x])&&fa!=k;rotate(x))
            if(f[fa])
                rotate((ch[f[x]][1]==x)==(ch[f[fa]][1]==fa)?fa:x);
    }
    inline void insert(int x)
    {
        if(!root)
        {
            ++ttt,clear(ttt),zhi[ttt]=x,cnt[ttt]++,root=ttt,update(root);
            return;
        }
        int now=root,fa=0;
        while(1)
        {
            if(zhi[now]==x)
            {
                cnt[now]++,update(now),update(fa),splay(now);
                return;
            }
            fa=now,now=ch[now][zhi[now]<x];
            if(!now)
            {
                ++ttt,clear(ttt),zhi[ttt]=x,cnt[ttt]++,f[ttt]=fa,ch[fa][zhi[fa]<x]=ttt;
                update(ttt),update(fa),splay(ttt);
                return;
            }
        }
        return;
    }
    inline int kth(int k)
    {
        int now=root;
        while(1)
        {
            if(ch[now][0]&&k<=size[ch[now][0]]) now=ch[now][0];
            else
            {
                k-=cnt[now]+size[ch[now][0]];
                if(k<=0) return splay(now),zhi[now];
                now=ch[now][1];
            }
        }
    }
    inline int rank(int k)
    {
        int now=root,res=0;
        while(1)
        {
            if(k<zhi[now]) now=ch[now][0];
            else
            {
                res+=size[ch[now][0]];
                if(k==zhi[now]) return splay(now),res+1;
                res+=cnt[now],now=ch[now][1];
            }
        }
    }
    inline int pre()
    {
        int now=ch[root][0];
        if(!now) return now;
        while(ch[now][1]) now=ch[now][1];
        return splay(now),now;
    }
    inline int nex()
    {
        int now=ch[root][1];
        if(!now) return now;
        while(ch[now][0]) now=ch[now][0];
        return splay(now),now;
    }
    inline void del(int x)
    {
        rank(x);
        if(cnt[root]>1)
        {
            cnt[root]--,update(root);
            return;
        }
        if(!ch[root][0]&&!ch[root][1])
        {
            clear(root),root=0;
            return;
        }
        if(!ch[root][0])
        {
            int now=root;
            root=ch[root][1],f[root]=0,clear(now);
            return;
        }
        if(!ch[root][1])
        {
            int now=root;
            root=ch[root][0],f[root]=0,clear(now);
            return;
        }
        int now=root,y=pre();
        f[ch[now][1]]=y,ch[y][1]=ch[now][1],clear(now),update(root);
        return;
    }
}tree;
int s[N];
int main()
{
    return 0;
}