Splay 伸展树

by 蒟蒻 XZY 2017.12.28

-1. 注

以下用数组模拟链表,不用指针。

未说明的情况下定义的节点结构体为:


struct N{int f,s[2],d,sz;}e[SIZE];

其中 $f$为父节点编号,$s[0]$为左儿子,$s[1]$为右儿子,$d$为该节点的值,$sz$为该节点大小。

$SIZE$为节点个数。

$0$号节点为空节点($NULL$)

还有一些定义:


int root;//根节点编号
int MKN();//make_new,新建一个节点,返回该节点编号
bool pos(int a);//position,获得该节点是其父节点左儿子还是右儿子(root 无关紧要)
void pup(int a);//push_up 节点 a
void pdown(int a);//push_down 节点 a
void rot(int a);//rotate,将节点 a 旋转到其父节点上方
void splay(int a,int t)//将节点 a splay 到节点 t 下方,作为 t 的儿子节点

一. 操作

0. 申请节点&垃圾回收

搞个栈就行了,复杂度 $O(1)$


int cnt;//新建节点个数
stack<int> st;//垃圾栈
int MKN()
{
    int tmp;
    if(st.empty())tmp=++cnt;
    else tmp=st.top(),st.pop();
    memset(&e[tmp],0,sizeof(N));//清空节点
    return tmp;
}

1. Build 操作

因为我们需要一颗平衡的树,所以我们每次找中间位置为子树的根,再递归建立左右子树(区间)。

复杂度 $O(n)$


int data[SIZE];
int build(int l,int r,int fa)
{
    if(l>r)return 0;
    int mid=(l+r)>>1,a=MKN();
    e[a].s[0]=build(l,mid-1,a),e[a].s[1]=build(mid+1,r,a);
    e[a].f=fa,e[a].d=data[mid],pup(a);
    return a;
}

2. Pos 操作

获取点 a 为左儿子(0)还是右儿子(1),很方便,因为在我的模板中节点的左右儿子分别为 $s[0],s[1]$,可以直接用这个操作获取下标。

复杂度 $O(1)$


bool pos(int a){return e[e[a].f].s[1]==a;}//还是很简便的=。=

3. Push_up 操作

一般来说就是类似递归地通过儿子更新父亲,如更新节点 a 的 sz

复杂度 $O(1)$


void pup(int a){e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+e[a].c;}

4. Push_down 操作

一般比较繁杂

但是谨记一个要点:

时刻保证你需要访问的节点是最新的!

就是更新某个节点的话,先手动改了这个节点的值,再给这个节点打上标记。

别只打标记,再在 push_down 中看是否有标记在更新这个节点,不然可能会错。


void pdown(int a)//这里实现的是子树整体加减某个值
{
    int l=e[a].s[0],r=e[a].s[1],t=e[a].tag;//tag 是标记域
    if(t!=0)//判断是否需要更新
    {
        if(l)e[l].tag+=t,e[l].d+=t;
        if(r)e[r].tag+=t,e[r].d+=t;
        e[a].tag=0;
    }
}

对于上面那个代码,比如我们要整棵树的值都加上 k,则:


void update(int k){if(root)e[root].tag+=k,e[root].d+=k;}

也就是先改值,再打标记

复杂度 $O(1)$

5. Rotate 操作

本来分为左旋、右旋,现在将其简化为:把节点 a 提到其父节点上方

复杂度 $O(1)$

见代码:


void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);//f:a 的父节点,g:a 的祖父节点
    pdown(f),pdown(a);//下传标记,f 在上所以先 push_down(f)
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;//要特判替换 a 位置的那个节点是否为空节点
    if(e[a].f=g)e[g].s[q]=a;//要特判 a 的祖父节点是否为空节点
    pup(f),pup(a);//更新节点信息,因为 f 在下所以先 push_up(f)
}

6. Splay 操作

整个 Splay 的核心,用来调整树的高度。

代码用 for 循环实现,很短,复杂度 $O(log_2n)$


void splay(int a,int t)
{
    for(;e[a].f!=t;rot(a))if(e[e[a].f].f!=t)
        if(pos(a)^pos(e[a].f))rot(a);
        else rot(e[a].f);
    if(!t)root=a;
}

注:上面代码若要旋到根则:$splay(a,0)$

7. Insert 操作

插入一个节点的操作,同二叉查找树。

只是插入完后记得 splay 那个新的节点。

复杂度 $O(log_2n)$


void insert(int d,int fa,int&a)//插入值为 d,fa 为父节点编号,a 是当前节点编号,注意用了 int&a
{
    if(!a){a=++cnt,e[a].f=fa,e[a].d=d,e[a].sz=e[a].c=1,splay(a,0);return;}
    pdown(a);
    if(d>e[a].d)insert(d,a,e[a].s[0]);
    else if(d<e[a].d)insert(d,a,e[a].s[1]);
    else e[a].c++,pup(a),splay(a,0);//如果值已经存在了就统计这种值出现次数(根据需求来)
}

8. 找第 k 大值操作

也和二叉查找树一样。

复杂度 $O(log_2n)$


int find_by_order(int k)//找第 k 大值,返回节点编号
{
    int a=root;
    while(a)
    {
        pdown(a);//千万记得 push_down 啊 QvQ
        if(k<=e[e[a].s[0]].sz)a=e[a].s[0];
        else
        {
            k-=e[e[a].s[0]].sz+e[a].c;
            if(k<=0)return a;
            a=e[a].s[1];
        }
    }
    return 0;//没找到,返回空节点
}

9. 提取区间操作

原理:二叉查找树的性质:左子树值< 父节点值< 右子树值。

设我们要提取区间 $[l,r]$

那我们就先将节点 $l-1$ Splay 到根,然后再把节点 $r+1$ Splay 到 $l-1$下面,这样以 $r+1$ 的左儿子为根的子树就是我们所要提取的区间了。所有区间 $[l,r]$中的元素都包含在该子树内。

因为可能出现提取整个区间的端点 ($1$或 $n$),但 $1-1$或者 $n+1$都越界了,所以我们需要在整个区间两端添加两个 “哨兵节点”

我习惯于设左边的哨兵节点编号为 $1$,右边的为 $n+2$,所以中间的原序列对应的节点编号都 $+1$了。

那么提取原序列区间 $[l,r]$的操作应该这么写:


void get_seg(int&l,int&r)
{
    l=find_by_order(l),r=find_by_order(r+2);
    splay(l,0),splay(r,l);
}

显然复杂度为 $O(log_2n)$

10. 插入区间

设我们要在第 $pos$个元素后面插入 $len$个元素($pos$为 $0$则插入在首部)

? 先把需要插入的元素放到 $data$数组中,然后提取区间 $[pos+1,pos+1]$ ,再把那 $len$个元素 $build$成一棵树,最后把这棵树接到刚刚提取出来的区间(空的区间)上,然后记得 push_up root 的右儿子和 root(要依次 push_up)。

复杂度 $O(n)$


int pos,len;
void work_insert()
{
    int l=pos+1,r=l;
    getstring(len),get_seg(l,r);//读入
    e[r].s[0]=build(0,len-1,r),pup(r),pup(l);
}

11. 删除区间

递归删除,复杂度 $O(n)$


void del_dfs(int a)//这是递归删除,不能直接调用
{
    if(!a)return;
    st.push(a),del_dfs(e[a].s[0]),del_dfs(e[a].s[1]);//丢到回收栈中
}
void work_del(int l,int r)//删除区间 [l,r] 的函数
{
    get_seg(l,r),del_dfs(e[r].s[0]),e[r].s[0]=0,pup(r),pup(root);
}

12. 翻转区间

先提取区间,然后更换区间对应的子树根的左右儿子,再给这个子树根打上标记。

复杂度 $O(log_2n)$


void pdown(int a)//push_down 要改了
{
    int l=e[a].s[0],r=e[a].s[1];
    if(e[a].rev)//rev 是翻转标记域
    {
        if(l)e[l].rev^=1,swap(e[l].s[0],e[l].s[1]);
        if(r)e[r].rev^=1,swap(e[r].s[0],e[r].s[1]);
        e[a].rev=0;
    }
}

void work_rev(int l,int r)//翻转区间 [l,r]
{
    get_seg(l,r);int p=e[r].s[0];
    if(p)swap(e[p].s[0],e[p].s[1]),e[p].rev^=1;
}

13. 输出区间

递归实现,复杂度 $O(n)$


void dfs_get(int a)//递归输出
{
    if(!a)return;
    dfs_get(e[a].s[0]),putchar(e[a].d),dfs_get(e[a].s[1]);
}
void work_get(int l,int r)//输出区间 [l,r]
{
    get_seg(l,r),dfs_get(e[r].s[0]),putchar('\n');
}

二. 习题&代码

0. 文艺平衡树

LOJ – 105,BZOJ – 3223

题解:传送门= ̄ω ̄=

代码:

#include <bits/stdc++.h>
#define NS (100005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,data[NS],sz,root;
struct N{int s[2],f,d,m,sz;}e[NS];
void pup(int a){e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+1;}
void pdown(int a)
{
    if(!e[a].m)return;
    e[e[a].s[0]].m^=1,e[e[a].s[1]].m^=1;
    swap(e[a].s[0],e[a].s[1]),e[a].m=0;
}
int build(int fa,int l,int r)
{
    if(l>r)return 0;
    int mid=(l+r)>>1,pos=++sz;
    e[pos].d=data[mid],e[pos].f=fa;
    e[pos].s[0]=build(pos,l,mid-1);
    e[pos].s[1]=build(pos,mid+1,r);
    pup(pos);
    return pos;
}
int jud(int a){return e[e[a].f].s[1]==a;}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=jud(a),q=jud(f);
    pdown(f),pdown(a);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    pup(f),pup(a);
}
void splay(int a,int t)
{
    while(e[a].f!=t)
    {
        if(e[e[a].f].f!=t)
        {
            if(jud(a)^jud(e[a].f))rot(a);
            else rot(e[a].f);
        }
        rot(a);
    }
    if(!t)root=a;
}
int find_by_order(int x)
{
    int a=root;
    while(a)
    {
        pdown(a);
        if(x<=e[e[a].s[0]].sz)a=e[a].s[0];
        else
        {
            x-=e[e[a].s[0]].sz+1;
            if(!x)return a;
            a=e[a].s[1];
        }
    }
    return 0;
}
void pans(int a)
{
    pdown(a);
    if(e[a].s[0])pans(e[a].s[0]);
    if(e[a].d!=-1e8&&e[a].d!=1e8)printf("%d ",e[a].d);
    if(e[a].s[1])pans(e[a].s[1]);
}
int main()
{
    IN(n),IN(m);
    for(int i=1;i<=n;i++)data[i+1]=i;
    data[1]=-1e8,data[n+2]=1e8,root=build(0,1,n+2);
    for(int i=1,l,r;i<=m;i++)
    {
        IN(l),IN(r),l=find_by_order(l),r=find_by_order(r+2);
        splay(l,0),splay(r,l);
        e[e[e[root].s[1]].s[0]].m^=1;
    }
    pans(root);
    return 0;
}

1. 序列终结者

BZOJ – 1251

题解:传送门= ̄ω ̄=

代码:

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct N{int s[2],f,d,rev,add,sz,mx;}e[50005];
int n,k,data[50005],sz,root;
bool pos(int a){return a==e[e[a].f].s[1];}
void pup(int a)
{
    e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+1;
    e[a].mx=max(e[a].d,max(e[e[a].s[0]].mx,e[e[a].s[1]].mx));
}
void pdown(int a)
{
    int&l=e[a].s[0],&r=e[a].s[1];
    if(e[a].add)
    {
        if(l)e[l].add+=e[a].add,e[l].d+=e[a].add,e[l].mx+=e[a].add;
        if(r)e[r].add+=e[a].add,e[r].d+=e[a].add,e[r].mx+=e[a].add;
        e[a].add=0;
    }
    if(e[a].rev)e[l].rev^=1,e[r].rev^=1,swap(l,r),e[a].rev=0;
}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);
    pdown(f),pdown(a);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    pup(f),pup(a);
}
void splay(int a,int t)
{
    for(;e[a].f!=t;rot(a))if(e[e[a].f].f!=t)
        if(pos(a)^pos(e[a].f))rot(a);
        else rot(e[a].f);
    if(!t)root=a;
}
int build(int l,int r,int f)
{
    if(l>r)return 0;
    int a=++sz,mid=(l+r)>>1;
    e[a].f=f,e[a].d=e[a].mx=data[mid];
    e[a].s[0]=build(l,mid-1,a),e[a].s[1]=build(mid+1,r,a);
    pup(a);
    return a;
}
int find_by_order(int x)
{
    int a=root;
    while(a)
    {
        pdown(a);
        if(x<=e[e[a].s[0]].sz)a=e[a].s[0];
        else
        {
            x-=e[e[a].s[0]].sz+1;
            if(!x)return a;
            a=e[a].s[1];
        }
    }
    return 0;
}
void get_part(int l,int r)
{
    l=find_by_order(l),r=find_by_order(r+2);
    splay(l,0),splay(r,l);
}
int main()
{
    IN(n),IN(k),e[0].mx=data[1]=data[n+2]=-2e9,root=build(1,n+2,0);
    for(int i=1,K,L,R,V,p;i<=k;i++)
    {
        IN(K),IN(L),IN(R),get_part(L,R),p=e[e[root].s[1]].s[0];
        if(K==1)IN(V),e[p].add+=V,e[p].d+=V,e[p].mx+=V;
        else if(K==2)e[p].rev^=1;
        else printf("%d\n",e[p].mx);
    }
    return 0;
}

2. 维修数列

BZOJ – 1500

题解:传送门= ̄ω ̄=

令人窒息の题目

代码:

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct N{int f,s[2],d,sum,lm,rm,mx,rev,tag,sz;}e[500005];
int n,m,data[500005],cnt,root;
char opt[10];
stack<int> st;
int MKN()
{
    int tmp;
    if(st.empty())tmp=++cnt;
    else tmp=st.top(),st.pop();
    memset(&e[tmp],0,sizeof(N)),e[tmp].tag=1e8;
    return tmp;
}
bool pos(int a){return e[e[a].f].s[1]==a;}
void pup(int a)
{
    int l=e[a].s[0],r=e[a].s[1];
    e[a].sz=e[l].sz+e[r].sz+1;
    e[a].sum=e[l].sum+e[r].sum+e[a].d;
    e[a].mx=max(e[l].mx,e[r].mx);
    e[a].mx=max(e[a].mx,e[l].rm+e[a].d+e[r].lm);
    e[a].lm=max(e[l].lm,e[l].sum+e[a].d+e[r].lm);
    e[a].rm=max(e[r].rm,e[r].sum+e[a].d+e[l].rm);
}
void pdown(int a)
{
    int l=e[a].s[0],r=e[a].s[1];
    if(e[a].tag!=1e8)
    {
        if(l)e[l].tag=e[l].d=e[a].tag,e[l].sum=e[a].tag*e[l].sz;
        if(r)e[r].tag=e[r].d=e[a].tag,e[r].sum=e[a].tag*e[r].sz;
        if(e[a].tag>=0)
        {
            if(l)e[l].lm=e[l].rm=e[l].mx=e[l].sum;
            if(r)e[r].lm=e[r].rm=e[r].mx=e[r].sum;
        }
        else
        {
            if(l)e[l].lm=e[l].rm=0,e[l].mx=e[a].tag;
            if(r)e[r].lm=e[r].rm=0,e[r].mx=e[a].tag;
        }
        e[a].tag=1e8;
    }
    if(e[a].rev)
    {
        if(l)e[l].rev^=1,swap(e[l].lm,e[l].rm),swap(e[l].s[0],e[l].s[1]);
        if(r)e[r].rev^=1,swap(e[r].lm,e[r].rm),swap(e[r].s[0],e[r].s[1]);
        e[a].rev=0;
    }
}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);
    pdown(f),pdown(a);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    pup(f),pup(a);
}
void splay(int a,int t)
{
    for(;e[a].f!=t;rot(a))if(e[e[a].f].f!=t)
        if(pos(a)^pos(e[a].f))rot(a);
        else rot(e[a].f);
    if(!t)root=a;
}
int build(int l,int r,int fa)
{
    if(l>r)return 0;
    int mid=(l+r)>>1,a=MKN();
    e[a].s[0]=build(l,mid-1,a),e[a].s[1]=build(mid+1,r,a);
    e[a].f=fa,e[a].d=data[mid],pup(a);
    return a;
}
int find_by_order(int k)
{
    int a=root;
    while(a)
    {
        pdown(a);
        if(k<=e[e[a].s[0]].sz)a=e[a].s[0];
        else
        {
            k-=e[e[a].s[0]].sz+1;
            if(!k)return a;
            a=e[a].s[1];
        }
    }
    return 0;
}
void get_part(int&l,int&r,int pos,int tot)
{
    l=find_by_order(pos),r=find_by_order(pos+tot+1);
    splay(l,0),splay(r,l);
}
void work_insert()
{
    int pos,tot,l,r;
    IN(pos),IN(tot);
    for(int i=1;i<=tot;i++)IN(data[i]);
    get_part(l,r,pos+1,0);
    e[r].s[0]=build(1,tot,r),pup(r),pup(root);
}
void del_dfs(int a)
{
    if(!a)return;
    st.push(a),del_dfs(e[a].s[0]),del_dfs(e[a].s[1]);
}
void work_del()
{
    int pos,tot,l,r;
    IN(pos),IN(tot),get_part(l,r,pos,tot);
    del_dfs(e[r].s[0]),e[r].s[0]=0,pup(r),pup(root);
}
void work_update()
{
    int pos,tot,l,r,c,p;
    IN(pos),IN(tot),IN(c),get_part(l,r,pos,tot),p=e[r].s[0];
    if(p)
    {
        e[p].d=e[p].tag=c,e[p].sum=e[p].sz*c;
        if(c>=0)e[p].lm=e[p].rm=e[p].mx=e[p].sum;
        else e[p].lm=e[p].rm=0,e[p].mx=c;
    }
    pup(r),pup(root);
}
void work_rev()
{
    int pos,tot,l,r,p;
    IN(pos),IN(tot),get_part(l,r,pos,tot),p=e[r].s[0];
    if(p)e[p].rev^=1,swap(e[p].lm,e[p].rm),swap(e[p].s[0],e[p].s[1]);
}
void work_sum()
{
    int pos,tot,l,r;
    IN(pos),IN(tot),get_part(l,r,pos,tot);
    printf("%d\n",e[e[r].s[0]].sum);
}
void work_max()
{
    int l=find_by_order(1),r=find_by_order(e[root].sz);
    splay(l,0),splay(r,l),printf("%d\n",e[e[r].s[0]].mx);
}
int main()
{
    IN(n),IN(m);
    for(int i=1;i<=n;i++)IN(data[i+1]);
    e[0].mx=data[1]=-1e8,data[n+2]=1e8,root=build(1,n+2,0);
    while(m--)
    {
        scanf("%s",opt);
        if(opt[0]=='I')work_insert();
        else if(opt[0]=='D')work_del();
        else if(opt[0]=='M')
        {
            if(opt[2]=='K')work_update();
            else work_max();
        }
        else if(opt[0]=='R')work_rev();
        else work_sum();
    }
    return 0;
}

3. 郁闷的出纳员

BZOJ – 1503

题解:传送门= ̄ω ̄=

好模板!就是有点坑,一开始工资就低于标准的人直接不算进入过公司。因为这个WA了好久啊!(>_<)

代码:

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct N{int f,s[2],d,c,tag,sz;}e[100005];
int n,m,root,cnt,K,ans;
char opt[5];
bool pos(int a){return e[e[a].f].s[1]==a;}
void pup(int a){e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+e[a].c;}
void pdown(int a)
{
    int l=e[a].s[0],r=e[a].s[1],t=e[a].tag;
    if(t!=0)
    {
        if(l)e[l].tag+=t,e[l].d+=t;
        if(r)e[r].tag+=t,e[r].d+=t;
        e[a].tag=0;
    }
}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);
    pdown(f),pdown(a);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    pup(f),pup(a);
}
void splay(int a,int t)
{
    for(;e[a].f!=t;rot(a))if(e[e[a].f].f!=t)
        if(pos(a)^pos(e[a].f))rot(a);
        else rot(e[a].f);
    if(!t)root=a;
}
void insert(int d,int fa,int&a)
{
    if(!a){a=++cnt,e[a].f=fa,e[a].d=d,e[a].sz=e[a].c=1,splay(a,0);return;}
    pdown(a);
    if(d>e[a].d)insert(d,a,e[a].s[0]);
    else if(d<e[a].d)insert(d,a,e[a].s[1]);
    else e[a].c++,pup(a),splay(a,0);
}
void update(int k){if(root)e[root].tag+=k,e[root].d+=k;}
int find_by_order(int k)
{
    int a=root;
    while(a)
    {
        pdown(a);
        if(k<=e[e[a].s[0]].sz)a=e[a].s[0];
        else
        {
            k-=e[e[a].s[0]].sz+e[a].c;
            if(k<=0)return a;
            a=e[a].s[1];
        }
    }
    return 0;
}
void check()
{
    while(e[root].sz)
    {
        int a=find_by_order(e[root].sz);
        if(splay(a,0),e[a].d>=m)break;
        ans+=e[a].c,e[e[a].s[0]].f=0,root=e[a].s[0];
    }
}
int main()
{
    IN(n),IN(m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",opt),IN(K);
        if(opt[0]=='I'){if(K<m)continue;insert(K,0,root),check();}
        else if(opt[0]=='A')update(K);
        else if(opt[0]=='S')update(-K),check();
        else    if(K>e[root].sz)puts("-1");
                    else printf("%d\n",e[find_by_order(K)].d);
    }
    printf("%d\n",ans);
    return 0;
}

4. Editor

BZOJ – 1507

题解:传送门= ̄ω ̄=

同 0. 维修数列,还简单些。

代码:

#include <bits/stdc++.h>
using namespace std;
struct N{int f,s[2],sz;char d;}e[2000000];
int t,P=1,cnt,root;
char opt[10],str[2000000];
bool pos(int a){return e[e[a].f].s[1]==a;}
void pup(int a){e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+1;}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    pup(f),pup(a);
}
void splay(int a,int t)
{
    for(;e[a].f!=t;rot(a))if(e[e[a].f].f!=t)
        if(pos(a)^pos(e[a].f))rot(a);
        else rot(e[a].f);
    if(!t)root=a;
}
int find_by_order(int k)
{
    int a=root;
    while(root)
    {
        if(k<=e[e[a].s[0]].sz)a=e[a].s[0];
        else
        {
            k-=e[e[a].s[0]].sz+1;
            if(!k)return a;
            a=e[a].s[1];
        }
    }
    return 0;
}
void get_seg(int&l,int&r)
{
    r+=l+1,l=find_by_order(l),r=find_by_order(r);
    splay(l,0),splay(r,l);
}
void getstring(int len)
{
    for(int i=0;i<len;i++)
        if((str[i]=getchar())=='\n'||str[i]=='\r'){i--;continue;}
    str[len]='\0';
}
int build(int l,int r,int fa)
{
    if(l>r)return 0;
    int mid=(l+r)>>1,a=++cnt;
    e[a].f=fa,e[a].d=str[mid];
    e[a].s[0]=build(l,mid-1,a),e[a].s[1]=build(mid+1,r,a),pup(a);
    return a;
}
void work_insert()
{
    int len,l=P,r=0;
    scanf("%d",&len),getstring(len),get_seg(l,r);
    e[r].s[0]=build(0,len-1,r),pup(r),pup(l);
}
void work_del()
{
    int l=P,r;
    scanf("%d",&r),get_seg(l,r),e[r].s[0]=0,pup(r),pup(l);
}
void dfs_get(int a)
{
    if(!a)return;
    dfs_get(e[a].s[0]),putchar(e[a].d),dfs_get(e[a].s[1]);
}
void work_get()
{
    int l=P,r;
    scanf("%d",&r),get_seg(l,r),dfs_get(e[r].s[0]),putchar('\n');
}
int main()
{
    scanf("%d",&t);
    root=1,cnt=2,e[1].s[1]=2,e[1].sz=2,e[2].f=1,e[2].sz=1;
    while(t--)
    {
        scanf("%s",opt);
        if(opt[0]=='M')scanf("%d",&P),P++;
        else if(opt[0]=='P')P--;
        else if(opt[0]=='N')P++;
        else if(opt[0]=='I')work_insert();
        else if(opt[0]=='D')work_del();
        else work_get();
    }
    return 0;
}

还有很多,不做过多赘述。

推荐习题列表

//注:题解不一定是 splay 的!n(≧▽≦)n

还有更多操作等待你的发现!

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

4 条评论

666 · 2019年4月10日 9:20 下午

哈哈,不错,算是这个小网站一个惊喜了,话说.moe 的域名我也好喜欢

    Remmina · 2019年4月14日 5:29 下午

    800 多篇文章还算小网站吗 QAQ

    Remmina · 2019年4月14日 5:31 下午

    而且这一篇并不是最好的呀,喜欢平衡树的话可以去了解一下 Leafy Tree 哇,站里有,搜就行了

    skydogli · 2019年6月27日 7:17 下午

    小网站你认真的吗

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注