splay——伸展树（哈！我也有不鸽的时候）

﹏ヽ暗。殇╰゛Y 2022-12-09 03:28 19阅读 0赞

其实说鸽就鸽，也是一种不鸽！

这是一种常用（对，就是常用，但是我才会的东西）的数据结构，主要用于插入删除，查看第k大，区间翻转.......操作（我目前就会几个简单的，后续会更新其他操作）

学习链接：[https://blog.csdn.net/ModestCoder\_/article/details/90139481][https_blog.csdn.net_ModestCoder_article_details_90139481]（这篇有推荐题）

[https://www.cnblogs.com/santiego/p/10011592.html][https_www.cnblogs.com_santiego_p_10011592.html]

[https://blog.csdn.net/Clove\_unique/article/details/50630280?utm\_medium=distribute.pc\_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel\_param&depth\_1-utm\_source=distribute.pc\_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel\_param][https_blog.csdn.net_Clove_unique_article_details_50630280_utm_medium_distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param_depth_1-utm_source_distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param]

这篇很详细

题目链接：[https://www.luogu.com.cn/problem/P3369][https_www.luogu.com.cn_problem_P3369]

我也不知道解释啥！我也挺迷的，反正就在保证结构特性的情况下随便转转就完事了，我能想通这样写为什么对，就是想不来如何创新

多看看上旋方式，如何避免链式最坏情况（有句话说的好对，没事就splay下），就能看懂为什么splay函数这么写了

后续会有区间翻转，虚实链剖分==内容更新

#include<bits/stdc++.h>
    using namespace std;
    const double pi = acos(-1.0);
    typedef long long ll;
    const ll mod =998244353;
    const int N=1e5+7;
    int sz;///当前节点个数
    int rt;///根节点编号
    int fa[N];///下标父亲节点编号
    int key[N];///编号i对应值
    int size[N];///编号i子树大小
    int num[N];///编号i重复次数
    int son[N][2];///编号i左右儿子 左0右1
    void clear(int x)///清除一个节点信息
    {
        fa[x]=key[x]=size[x]=num[x]=son[x][0]=son[x][1]=0;
    }
    int get(int x)///确定一个节点是父亲的左儿子还是右儿子
    {
        if(son[fa[x]][0]==x) return 0;
        return 1;
    }
    void update(int x)///更新一个节点size
    {
        if(x)
        {
            size[x]=num[x];
            if(son[x][0]) size[x]+=size[son[x][0]];
            if(son[x][1]) size[x]+=size[son[x][1]];
        }
    }
    void link(int x,int y,int z)///x连在y下面关系为z
    {
        if(x) fa[x]=y;
        if(y) son[y][z]=x;
    }
    void rotate(int x)///旋转，与自己的父亲交换位置
    {
        int ffa=fa[x],fffa=fa[ffa],m=get(x),n=get(ffa);
        link(son[x][m^1],ffa,m);
        link(ffa,x,m^1);
        link(x,fffa,n);
        update(ffa);update(x);
    }
    void splay(int x)///讲一个节点上旋至根节点
    {
        for(int ffa;ffa=fa[x];rotate(x))///为了避免链式结构，需要判断，选择上旋方式
            if(fa[ffa])
            {
            if(get(x)==get(ffa))
                rotate(ffa);
            else
                rotate(x);
            }
            rt=x;
    }
    void insert(int x)///插入节点，新节点上旋至根节点保证整体的平衡
    {
        if(!rt)
        {
            rt=++sz;
            key[rt]=x;
            size[rt]=num[rt]=1;
            son[rt][0]=son[rt][1]=0;
            return ;
        }
        int now=rt,ffa=0;
        while(1)
        {
            if(key[now]==x)
            {
                num[now]++;
                update(now);
                update(ffa);
                splay(now);
                return;
            }
            ffa=now;
            now=son[now][x>key[now]];
            if(!now)
            {
                ++sz;
                key[sz]=x;
                size[sz]=num[sz]=1;
                fa[sz]=ffa;
                son[ffa][x>key[ffa]]=sz;
                update(ffa);
                splay(sz);
                return;
            }
        }
    }
    int find(int x)
    {
        int now=rt,ans=0;
        while(1)
        {
           if(x<key[now])
           {
               now=son[now][0];
               continue;
           }
           ans+=size[son[now][0]];
           if(x==key[now]) {splay(now);return ans+1;}
           ans+=num[now];
           now=son[now][1];
        }
    }
    int findk(int x)
    {
        int now=rt;
        while(1)
        {
            if(son[now][0]&&x<=size[son[now][0]])
            {
                now=son[now][0];continue;
            }
            if(son[now][0]) x-=size[son[now][0]];
            if(x<=num[now]) {splay(now);return key[now];}
            x-=num[now];
            now=son[now][1];
        }
    }
    int pre()///返回当前树左子树最大值（根节点前驱
    {
        int now=son[rt][0];
        while(son[now][1]) now=son[now][1];
        return now;
    }
    int nxt()///返回当前树右子树最小值（根节点后继
    {
        int now=son[rt][1];
        while(son[now][0]) now=son[now][0];
        return now;
    }
    void del(int x)///
    {
        int nouse=find(x);
        if(num[rt]>1)
        {
            --num[rt];
            update(rt);
            return;
        }
        if(!son[rt][0]&&!son[rt][1])///只有一个节点
        {
            clear(rt);
            rt=0;
            return;
        }
        if(!son[rt][0])///只有一个儿子的情况
        {
            int tmp=rt;
            rt=son[rt][1];
            fa[rt]=0;
            clear(tmp);
            return;
        }
        if(!son[rt][1])
        {
            int tmp=rt;
            rt=son[rt][0];
            fa[rt]=0;
            clear(tmp);
            return;
        }
        ///左右儿子都健在的情况，吧pre上旋至根，要删的节点会变成只有右儿子的情况，这就好搞了啊
        int tmp=rt;
        int left=pre();
        splay(left);
        link(son[tmp][1],rt,1);
        clear(tmp);
        update(rt);
    }
    int main()
    {
        ios::sync_with_stdio(false);
      int q;
      cin>>q;
      while(q--)
      {
          int choose,x;
          cin>>choose>>x;
          if(choose==1) insert(x);
          if(choose==2) del(x);
          if(choose==3) {cout<<find(x)<<endl;}
          if(choose==4) {cout<<findk(x)<<endl;}
          if(choose==5) {insert(x);cout<<key[pre()]<<endl;del(x);}
          if(choose==6) {insert(x);cout<<key[nxt()]<<endl;del(x);}
      }
    }

第二个例题文艺平衡树，就是splay的区间翻转，（当然还可以用分块莽过去，分块多好告，真的是，用splay干嘛~！）

我们先建一颗权值splay，如果要翻转一个区间，只需要吧l-1翻到root，r+1翻到root的右儿子，r+1的左子树就是要翻转的区间

加上一个tag标记就完事了（和线段树的lazy一个吊样），之后在找下一个l-1和r+1执行操作，找的时候肯定是从root开始找的，如果当前节点有tap，就pushdown下去，交换左右儿子，tag标记顺移下去就完事了，最后终须遍历一下就完事了

第三个例题 排序机械臂

题目链接：[https://www.luogu.com.cn/problem/P3165][https_www.luogu.com.cn_problem_P3165]

区间反转而已，只是需要一点思维（我木得脑子，我看的题解改的）先排序，原数组里面的值就没用了，只用维护排序后的相对顺序就好了，二叉树建权值splay，维护下标，然后按顺序把节点翻到rt，左子树个数就是第几位（因为后面有区间修改，所以有两个哨兵）然后就是区间翻转的板子了（魔改了半天，还改的效率愈发低下了）

[https_blog.csdn.net_ModestCoder_article_details_90139481]: https://blog.csdn.net/ModestCoder_/article/details/90139481
[https_www.cnblogs.com_santiego_p_10011592.html]: https://www.cnblogs.com/santiego/p/10011592.html
[https_blog.csdn.net_Clove_unique_article_details_50630280_utm_medium_distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param_depth_1-utm_source_distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param]: https://blog.csdn.net/Clove_unique/article/details/50630280?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param
[https_www.luogu.com.cn_problem_P3369]: https://www.luogu.com.cn/problem/P3369
[https_www.luogu.com.cn_problem_P3165]: https://www.luogu.com.cn/problem/P3165