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;
}
还有很多，不做过多赘述。
推荐习题列表
- 营业额统计 BZOJ – 1588 题解：传送门=￣ω￣=
- 永无乡 BZOJ – 2733 题解：传送门=￣ω￣=
- 普通平衡树 BZOJ – 3224 题解：传送门=￣ω￣=
- 弹飞绵羊 BZOJ – 2002 题解：传送门=￣ω￣= //lct
- 洞穴勘测 BZOJ – 2049 题解：传送门=￣ω￣= //lct
- 【模板】Link Cut Tree LUOGU – 3690 题解：传送门=￣ω￣= //lct
//注：题解不一定是 splay 的！n(≧▽≦)n
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 下午
小网站你认真的吗