给新高一小朋友讲 splay

IamTZYwhoAKedIOI · 2025-07-11 23:48:33 · 算法·理论

树形数据结构简介及分类

1. 树形：
2. 数据结构：
3. 分类：
   • Leafy：只有叶子节点维护的是原始的信息，非叶子节点维护子树信息总和。例：线段树，WBLT。
   • Nody：每个节点上都维护了原始信息，并且也维护了子树信息总和。例：splay，树状数组，堆。

splay 的应用一

P6136

一个节点需要维护哪些东西

1. l：左子节点的指针；
2. r：右子节点的指针；
3. n：数字；
4. cnt：该数字出现次数；
5. sz：子树大小；
6. maxn：子树中最大数。

pushup

旋转操作

splay 板子

splay 的应用一的基本操作包括：

• lower_bound
• kth

参考实现

#include<stdio.h>
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
struct node
{
    node*l,*r;int n,cnt,sz,maxn;
}*rt;
int n,m,ans,lstans;
inline void pu(node*i)
{
    i->sz=i->cnt;
    if(i->l)i->sz+=i->l->sz;
    if(i->r)i->sz+=i->r->sz,i->maxn=i->r->maxn;
    else i->maxn=i->n;
}
inline node*L(node*i){node*j=i->r;i->r=j->l;j->l=i;pu(i);pu(j);return j;}
inline node*R(node*i){node*j=i->l;i->l=j->r;j->r=i;pu(i);pu(j);return j;}
inline char lslay(node*&i,int x)
{
    if(i->l)if(x<=i->l->maxn)
    {
        char o=lslay(i->l,x);
        if(o&1){i=R(i);i=R(i);return 0;}
        if(o&2){i->l=L(i->l);i=R(i);return 0;}
        return 1;
    }
    if(x<=i->n||!i->r)return 0;
    char o=lslay(i->r,x);
    if(o&2){i=L(i);i=L(i);return 0;}
    if(o&1){i->r=R(i->r);i=L(i);return 0;}
    return 2;
}
inline void lsplay(node*&i,int x)
{
    char o=lslay(i,x);
    if(o&1)i=R(i);
    if(o&2)i=L(i);
}
inline void isplay(node*&i,int x)
{
    lsplay(i,x);
    if(i->n==x)++i->cnt,++i->sz;
    else
    {
        lsplay(i->l,1<<30);
        i->l->r=new node{0,0,x,1,1,x};
        pu(i->l);pu(i);
    }
}
inline char slay(node*&i,int x)
{
    if(i->l)if(x<=i->l->sz)
    {
        char o=slay(i->l,x);
        if(o&1){i=R(i);i=R(i);return 0;}
        if(o&2){i->l=L(i->l);i=R(i);return 0;}
        return 1;
    }
    if(i->l)x-=i->l->sz;
    if(x<=i->cnt)return 0;
    x-=i->cnt;
    char o=slay(i->r,x);
    if(o&2){i=L(i);i=L(i);return 0;}
    if(o&1){i->r=R(i->r);i=L(i);return 0;}
    return 2;
}
inline void splay(node*&i,int x)
{
    char o=slay(i,x);
    if(o&1)i=R(i);
    if(o&2)i=L(i);
}
main()
{
    read(n);read(m);
    rt=new node{0,0,-1,1,1,-1};rt=new node{rt,0,1<<30,1,0,0};pu(rt);
    for(int x;n--;read(x),isplay(rt,x));
    for(int o,x;m--;)switch(read(o),read(x),x^=lstans,o)
    {
        case 1:isplay(rt,x);break;
        case 2:lsplay(rt,x);--rt->cnt;
            if(!rt->cnt)splay(rt->r,1),rt->r->l=rt->l,rt=rt->r;break;
        case 3:lsplay(rt,x);ans^=lstans=rt->l->sz;break;
        case 4:splay(rt,x+1);ans^=lstans=rt->n;break;
        case 5:lsplay(rt,x);lsplay(rt->l,1<<30);ans^=lstans=rt->l->n;break;
        case 6:lsplay(rt,x+1);ans^=lstans=rt->n;
    }
    printf("%d",ans);
}

splay 的应用二

P3391

和上个题相比少了很多东西，多了很少东西：

注意到这里的翻转操作需要打 tag，众所周知 tag 需要下传，应该是大家学线段树的时候就熟悉的。

参考实现

#include<stdio.h>
#include<bits/stl_algobase.h>
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
struct node
{
    node*l,*r;int x,sz;bool f;
}*rt;
inline void pu(node*i)
{
    i->sz=1;
    if(i->l)i->sz+=i->l->sz;
    if(i->r)i->sz+=i->r->sz;
}
inline void pd(node*i)
{
    if(!i->f)return;
    i->f=0;
    if(i->l)
    {
        i->l->f^=1;
        swap(i->l->l,i->l->r);
    }
    if(i->r)
    {
        i->r->f^=1;
        swap(i->r->l,i->r->r);
    }
}
inline node*L(node*i)
{
    pd(i);
    node*j=i->r;pd(j);
    i->r=j->l;j->l=i;pu(i);pu(j);
    return j;
}
inline node*R(node*i)
{
    pd(i);
    node*j=i->l;pd(j);
    i->l=j->r;j->r=i;pu(i);pu(j);
    return j;
}
inline char slay(node*&i,int x)
{
    pd(i);
    if(i->l)if(i->l->sz>=x)
    {
        char o=slay(i->l,x);
        if(o&1){i=R(i);i=R(i);return 0;}
        if(o&2){i->l=L(i->l);i=R(i);return 0;}
        return 1;
    }
    if(i->l)x-=i->l->sz;
    if(x==1)return 0;
    char o=slay(i->r,x-1);
    if(o&2){i=L(i);i=L(i);return 0;}
    if(o&1){i->r=R(i->r);i=L(i);return 0;}
    return 2;
}
inline void splay(node*&i,int x)
{
    char o=slay(i,x);
    if(o&1)i=R(i);
    if(o&2)i=L(i);
}
main()
{
    int n,m;
    read(n);read(m);
    for(int i=1;i<=n;++i)rt=new node{rt,0,i,i,0};
    for(int l,r;m--;)
    {
        read(l);read(r);
        node*i;
        if(l==1)if(r==n)i=rt;
        else splay(rt,r+1),i=rt->l;
        else
        {
            splay(rt,l-1);
            if(r==n)i=rt->r;
            else splay(rt->r,r-l+2),i=rt->r->l;
        }
        i->f^=1;
        swap(i->l,i->r);
    }
    for(int i=1;i<=n;++i)splay(rt,i),printf("%d ",rt->x);
}

splay 的应用三

P3165

不打算讲。

习题

P5066