Splay总结
xzyxzy
2018-02-03 21:49:06
#**伸展树(Splay)**
Tags:数据结构
##更好阅读体验：https://www.zybuluo.com/xzyxzy/note/1004417
----------
##**一、基本内容**
yyb博客：http://www.cnblogs.com/cjyyb/p/7499020.html
基本类型：平衡树（树深度期望是log的）二叉搜索树（中序遍历为从小到大）
核心思想：不断把查询过的点转到根，尽可能打乱顺序使其尽量接近期望复杂度
(萝卜说研究表明90%的询问都集中在10%的数据中，所以Splay十分难被卡)
----------
##**二、题目**
###**1、练基础**
P3369 【模板】普通平衡树 https://www.luogu.org/problemnew/show/3369
P2286 [HNOI2004]宠物收养场 https://www.luogu.org/problemnew/show/2286
P2234 [HNOI2002]营业额统计 https://www.luogu.org/problemnew/show/2234
P2073 送花 https://www.luogu.org/problemnew/show/P2073
###**2、刷提高**
P3224 [HNOI2012]永无乡 https://www.luogu.org/problemnew/show/3224
P1486 [NOI2004]郁闷的出纳员 https://www.luogu.org/problemnew/show/P1486
P3391 【模板】文艺平衡树https://www.luogu.org/problemnew/show/P3391
P2596 [ZJOI2006]书架 https://www.luogu.org/problemnew/show/P2596
P2584 [ZJOI2006]GameZ游戏排名系统 [https://www.luogu.org/show/P2584][1]
P3201 [HNOI2009]梦幻布丁([题解][2]) [https://www.luogu.org/show/3201][3]
###**3、变态题**
P3165 [CQOI2014]排序机械臂 https://www.luogu.org/problemnew/show/P3165
P2042 [NOI2005]维护数列 https://www.luogu.org/problemnew/show/P2042
---
##**三、做题经验**
###**1、支持的操作**
###**对于点**
>A、插/删点
详见后方区间操作
>B、动态查询某数(结点)前驱后继
用Next函数实现，原理是把需要查询的数转到根，再在其右子树的最左端查后继，左子树的最右段查前驱
>C、查询排名为k的数/查询k的排名
k的排名那么把k转到根，左子树大小便是k的排名，见代码110-120行，很好理解
###**对于区间**
**每次将要访问到儿子结点的时候都要pushdown！！**
>A、插/删区间
把要插入的位置的前一个数绕到根，后一个数绕到根的右儿子，然后把插入的区间建成一棵splay连到后一个数的左儿子上
用$l$的前驱转到根，$r$后继转到$l$前驱的儿子，然后后继的左儿子那一段就是要删的点，直接去掉
>B、区间翻转
**翻转一个区间，颠覆了Splay按权值排序的概念**
具体操作就是翻转一个区间，相当于把所有结点的左右儿子交换
那么打一个标记，当要修改时pushdown就好了(好像和线段树了懒标记有点像哦)
**建议把标记定义成已经翻转了该点的左右儿子！[这里是模板！][4][这里有难题！][5]**
>C、区间覆盖
>D、区间求和
>E、求数列最大子段和
详见下方维护数列的code
>F、区间加法
自己yy一下应该可以弄出来
**由此可见，splay可以代替线段树的所有操作！**
**但是，越通用的算法常数越大！**
**大致可以理解为 splay>线段树>树状数组**
###**还有呢**
>Splay合并
这个嘛不太好说，启发式合并好了，梦幻布丁和永无乡都是的
##**Splay模板**
```cpp
//https://www.luogu.org/problemnew/show/P3369
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int read()
{
char ch=getchar();
int h=0,t=1;
while(ch!='-'&&(ch>'9'||ch<'0'))ch=getchar();
if(ch=='-'){ch=getchar();t=-1;}
while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
return h*t;
}
int n,tot,root;
struct Splay{int fa,val,cnt,siz,ch[2];}t[100011];
void pushup(int x)
{
t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].cnt;
}
void rotate(int x)//把x的父亲变成它儿子
{
int y=t[x].fa,z=t[y].fa;
int k=t[y].ch[1]==x;//表示x是y的 0左儿子 1右儿子
//Step1 把x和z相连(相同)
t[z].ch[t[z].ch[1]==y]=x;//y位置
t[x].fa=z;
//Step2 把x的儿子丢给y(相反)
t[y].ch[k]=t[x].ch[k^1];
t[t[x].ch[k^1]].fa=y;
//Step3 把y搞成x的儿子(相反)
t[x].ch[k^1]=y;
t[y].fa=x;
pushup(y);//更新！！
//注意顺序！！！！！
}
void splay(int x,int fa)//把x旋转成fa的儿子(fa=0则旋转到根)
{
while(t[x].fa!=fa)
{
int y=t[x].fa,z=t[y].fa;
if(z!=fa)(t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y);
rotate(x);
}
if(!fa)root=x;
pushup(x);//更新！！(放在这里常数会小些)
/*
这是重点！敲黑板！
把x旋转到根，这一步保证了双旋，近似可以理解为rand了一下链(可以自己画一下单旋，会发现单旋的旧链没有改变，复杂度会被卡)于是这样之后更接近了期望复杂度NlogN
双旋要求x祖父不是将要成为x父亲的结点(如果是的而且旋转了y那么z成为y儿子，x永远无法成为z的儿子),而且当从祖父到x一直是左儿子或者一直是右儿子就可以转y了,并且每一步最后都必须动x,在前面选择的时候，如果不同时为左儿子或右儿子，那么动y并不会将x向上提，没有效果
在每一步最后，如果不动x而是一直动y，那么y上方的旧链会出现在y右儿子的左儿子上
每一步都是精心打造，目的是让树尽可能随机重构，来平衡其期望复杂度,如果有任何疑问，手玩一棵Splay就会发现去掉某一句都会使Splay出现旧链或效率变低
*/
}
void Insert(int num)//把num加入Splay树
{
int x=root,fa=0;
while(x&&t[x].val!=num)
{
fa=x;//向下找
x=t[x].ch[num>t[x].val];//大于向右，小于向左
}
if(x){t[x].cnt++;splay(x,0);return;}//新点非根
x=++tot;
if(fa)t[fa].ch[num>t[fa].val]=x;
t[x]=(Splay){fa,num,1,1,{0,0}};
splay(x,0);//把当前位置移到根，保证结构的平衡
//还有一个作用，更新了x的树大小，那么要一路更新上去
}
void find(int num)//找到num的位置并把它旋转到根
{
int x=root;if(!x)return;
while(t[x].ch[num>t[x].val]&&num!=t[x].val)
x=t[x].ch[num>t[x].val];
splay(x,0);//旋转到根
}
int Next(int num,int f)//查找num的前驱(0)或后继(1)
{
find(num);int x=root;
if(t[x].val>num&&f)return x;//当前结点大于x且查询后继
if(t[x].val<num&&!f)return x;//当前结点小于x且查询前驱
x=t[x].ch[f];//后继在右子树，前驱在左子树
while(t[x].ch[f^1])x=t[x].ch[f^1];//反着找
return x;
}
void Delete(int num)//删除num(同理也可以删除区间)
{
int last=Next(num,0),next=Next(num,1);
splay(last,0);splay(next,last);
//查找l的前驱和r的后继，把前驱转到根，后继转到根的下面
//那么l到r这段区间里所有数就是在后继的左儿子上了
int pos=t[next].ch[0];
if(t[pos].cnt>1)
{
t[pos].cnt--;
splay(pos,0);
}
else
{
t[next].ch[0]=0;//丢掉！
pushup(next);pushup(last);//要记得更新呦～
}
}
int Query1Rank(int num)//查找num的编号
{
find(num);
return t[t[root].ch[0]].siz;
}
int Query2Rank(int num)//查找编号为num的数
{
int x=root;if(t[x].siz<num)return 0;
while(1)
{
int Size=t[t[x].ch[0]].siz,Cnt=t[x].cnt;
if(num>Size&&num<=Size+Cnt)return t[x].val;
if(num<=Size)x=t[x].ch[0];
if(num>Size+Cnt){num-=Size+Cnt;x=t[x].ch[1];}//注意顺序
}
}
int main()
{
n=read();
Insert(+2147483647);
Insert(-2147483647);//便于找到前驱后继
for(int i=1;i<=n;i++)
{
int opt=read(),x=read();
if(opt==1){Insert(x);}
if(opt==2){Delete(x);}
if(opt==3){printf("%d\n",Query1Rank(x));}
if(opt==4){printf("%d\n",Query2Rank(x+1));}
if(opt==5){printf("%d\n",t[Next(x,0)].val);}
if(opt==6){printf("%d\n",t[Next(x,1)].val);}
}
return 0;
}
```
##**维护数列**
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cstring>
#define RG register
using namespace std;
inline int read()
{
RG char ch=getchar();
RG int h=0,t=1;
while(ch!='-'&&(ch>'9'||ch<'0'))ch=getchar();
if(ch=='-'){t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){h=(h<<3)+(h<<1)+ch-'0';ch=getchar();}
return h*t;
}
const int MAXN=500100;
int N,M,root,tot;
struct Splay
{
int val,fa,siz,ch[2];
int sum,lx,rx,mx;
bool mark,lazy;
//bool u;
}t[MAXN];
queue<int>Q;//内存池
int pos,all,c;
int a[MAXN],zhan[MAXN],top;
/*
inline void Printtree()
//功能：调试输出Splay
{
tot=0;
printf("root=%d\n",root);
for(RG int i=1;i<=MAXN-1;i++)
if(t[i].u)
tot++,printf("#%2d: fa=%2d,siz=%2d,mark=%2d,lazy=%2d,val=%2d,sum=%2d,lc=%2d,rc=%2d,lx=%2d,rx=%2d,mx=%2d\n",i,t[i].fa,t[i].siz,t[i].mark,t[i].lazy,t[i].val,t[i].sum,t[i].ch[0],t[i].ch[1],t[i].lx,t[i].rx,t[i].mx);
printf("tot=%d\n",tot);
}
*/
inline Splay Get(RG int v,RG int f,RG int u)
//功能：见下，初始化一个结点
{
RG Splay R;
R.val=v;R.fa=f;R.siz=u;R.ch[0]=0;R.ch[1]=0;
R.mark=0;R.lazy=0;R.sum=v;
R.lx=max(0,v);R.rx=max(0,v);R.mx=u?v:-1e9;
//R.u=u;
return R;
}
inline void pushup(RG int x)
//功能：由下往上更新x结点的一些内容
{
t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1;
t[x].sum=t[t[x].ch[0]].sum+t[t[x].ch[1]].sum+t[x].val;
t[x].lx=max(t[t[x].ch[0]].lx,t[t[x].ch[0]].sum+t[x].val+t[t[x].ch[1]].lx);
t[x].rx=max(t[t[x].ch[1]].rx,t[t[x].ch[1]].sum+t[x].val+t[t[x].ch[0]].rx);
t[x].mx=max(max(t[t[x].ch[0]].mx,t[t[x].ch[1]].mx),t[t[x].ch[0]].rx+t[x].val+t[t[x].ch[1]].lx);
//留坑:当一个点没有右儿子然后mx必须为负数的时候，由此程序跑出来mx=0，但已通过的程序大部分都没判，故留坑
}
inline void pushdown(RG int x)
//功能：由上往下下放一些标记
{
if(t[x].lazy)//lazy表示已经改变了当前结点的值
{
t[x].lazy=0;t[x].mark=0;
if(t[x].ch[0]){t[t[x].ch[0]].val=t[x].val;t[t[x].ch[0]].sum=t[t[x].ch[0]].siz*t[x].val;t[t[x].ch[0]].lazy=1;}
if(t[x].ch[1]){t[t[x].ch[1]].val=t[x].val;t[t[x].ch[1]].sum=t[t[x].ch[1]].siz*t[x].val;t[t[x].ch[1]].lazy=1;}
if(t[x].val>=0)
{
if(t[x].ch[0]){t[t[x].ch[0]].lx=t[t[x].ch[0]].rx=t[t[x].ch[0]].mx=t[t[x].ch[0]].sum;}
if(t[x].ch[1]){t[t[x].ch[1]].lx=t[t[x].ch[1]].rx=t[t[x].ch[1]].mx=t[t[x].ch[1]].sum;}
}
else
{
if(t[x].ch[0]){t[t[x].ch[0]].lx=t[t[x].ch[0]].rx=0;t[t[x].ch[0]].mx=t[x].val;}
if(t[x].ch[1]){t[t[x].ch[1]].lx=t[t[x].ch[1]].rx=0;t[t[x].ch[1]].mx=t[x].val;}
}
}
if(t[x].mark)//mark表示已经交换了当前结点的左右儿子
{
t[x].mark=0;
if(t[x].ch[0])t[t[x].ch[0]].mark^=1;
if(t[x].ch[1])t[t[x].ch[1]].mark^=1;
swap(t[t[x].ch[0]].lx,t[t[x].ch[0]].rx);
swap(t[t[x].ch[1]].lx,t[t[x].ch[1]].rx);
//Attention:上面左儿子和右儿子的左右右子段交换，画图稍微模拟一下
swap(t[t[x].ch[0]].ch[0],t[t[x].ch[0]].ch[1]);
swap(t[t[x].ch[1]].ch[0],t[t[x].ch[1]].ch[1]);
}
}
inline void Find(RG int x)
//功能：把从root到x的路径一直pushdown
{
top=0;zhan[++top]=x;
if(x==root){pushdown(x);return;}
while(t[x].fa!=root){zhan[++top]=t[x].fa;x=t[x].fa;}
zhan[++top]=root;
while(top){pushdown(zhan[top]);top--;}
}
inline void rotate(RG int x)
//功能：把x旋转成x父亲的父亲
{
RG int y=t[x].fa,z=t[y].fa;
RG int k=t[y].ch[1]==x;
t[z].ch[t[z].ch[1]==y]=x; t[x].fa=z;
t[y].ch[k]=t[x].ch[k^1]; t[t[x].ch[k^1]].fa=y;
t[x].ch[k^1]=y; t[y].fa=x;
pushup(y);
}
inline void splay(RG int x,RG int fa)
//功能：把x旋转成为fa的儿子
{
Find(x);
while(t[x].fa!=fa)
{
RG int y=t[x].fa,z=t[y].fa;
if(z!=fa)(t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
rotate(x);
}
if(!fa)root=x;
pushup(x);
}
inline int Buildtree(RG int l,RG int r,RG int fa)
//功能：a[l]到a[r]之间建立以fa为根的父亲的Splay并返回其根的结点编号
{
if(l>r)return 0;
RG int x=Q.front();Q.pop();//从内存池中取出编号
if(l==r){t[x]=Get(a[l],fa,1);return x;}
RG int mid=(l+r)>>1;
t[x]=Get(a[mid],fa,1);
t[x].ch[0]=Buildtree(l,mid-1,x);
t[x].ch[1]=Buildtree(mid+1,r,x);
pushup(x);return x;
}
inline int Kth(RG int num)
//功能：在Splay中找到第num个数并返回结点编号
{
RG int x=root;
while(1)
{
pushdown(x);
RG int Size=t[t[x].ch[0]].siz;
if(num<=Size)x=t[x].ch[0];
if(num==Size+1)return x;
if(num>Size+1){num-=Size+1;x=t[x].ch[1];}
}
}
inline void Insert(RG int pos,RG int all)
//功能：在第pos+1个数后插入all个数(哨兵影响)
{
for(RG int i=1;i<=all;i++)a[i]=read();
RG int x=Kth(pos+1),next=Kth(pos+2);
splay(x,0);//pushdown(x);
splay(next,x);//pushdown(next);
t[next].ch[0]=Buildtree(1,all,next);
pushup(next);pushup(x);
}
inline void Recycle(RG int x)
//功能：回收以x为根的子树中所有结点
{
if(!x)return;
if(t[x].ch[0])Recycle(t[x].ch[0]);
if(t[x].ch[1])Recycle(t[x].ch[1]);
t[x]=Get(0,0,0);Q.push(x);
}
inline void Work(RG int pos,RG int all,RG int op)
//功能：表示对区间[pos+1,pos+all]的操作(由于两个哨兵)
// op=1删除 op=2区间覆盖
// op=3翻转 op=4求和
{
if(all==0){if(op==2)read();if(op==4)printf("0\n");return;}
//printf("[%d,%d]进行%d\n",pos+1,pos+all,op);
RG int last=Kth(pos),next=Kth(pos+all+1);
splay(last,0);//pushdown(last);
splay(next,last);//pushdown(next);
//这里不需要因为splay(x)的时候已经pushdown(x)了
RG int x=t[next].ch[0];
if(op==1)
{
Recycle(x);
t[next].ch[0]=0;
}
if(op==2)
{
c=read();t[x].lazy=1;
t[x].val=c;t[x].sum=t[x].siz*c;
if(c>=0){t[x].lx=t[x].rx=t[x].mx=t[x].sum;}
else{t[x].lx=t[x].rx=0;t[x].mx=c;}
}
if(op==3&&!t[x].lazy)
{
t[x].mark^=1;
swap(t[x].lx,t[x].rx);
swap(t[x].ch[0],t[x].ch[1]);
}
if(op==4)printf("%d\n",t[x].sum);
pushup(next);pushup(last);
}
int main()
{
freopen("seq2005.in","r",stdin);
freopen("seq2005.out","w",stdout);
N=read();M=read();
t[0].mx=a[1]=a[N+2]=-1e9;
t[0].val=t[0].fa=t[0].siz=t[0].mark=t[0].lazy=0;
t[0].sum=t[0].ch[0]=t[0].ch[1]=t[0].lx=t[0].rx=0;
for(RG int i=1;i<=MAXN-1;i++)Q.push(i);
for(RG int i=1;i<=N;i++)a[i+1]=read();//左右哨兵
root=Buildtree(1,N+2,0);
for(RG int i=1;i<=M;i++)
{
RG char s[20];scanf("%s",s);
//printf("%s\n",s);
if(s[0]!='M'||s[2]=='K'){pos=read();all=read();}
if(s[0]=='I')Insert(pos,all);//在pos后加入all个数
if(s[0]=='D')Work(pos,all,1);//在pos后删去all个数
if(s[0]=='M')
{
if(s[2]=='K')Work(pos,all,2);//区间覆盖
else printf("%d\n",t[root].mx);//最大子段和
}
if(s[0]=='R')Work(pos,all,3);//翻转
if(s[0]=='G')Work(pos,all,4);//求和
//Printtree();
}
return 0;
}
```
[1]: https://www.luogu.org/problemnew/show/P2584
[2]: http://www.cnblogs.com/cjyyb/p/7678275.html
[3]: https://www.luogu.org/problemnew/show/3201
[4]: https://www.luogu.org/recordnew/show/5291137
[5]: https://www.luogu.org/problemnew/show/P3165