splay小结—植树结
我要把高级数据结构当爸爸了... ...弱到跪烂了。
splay，二叉搜索树的一种，具有稳定变形功能。
二叉搜索树：对于一个节点，都只有不超过2个孩子。其左子树内的点的权值都比这个点小，右子树的点的权值都比这个点要大(等于的话随你)。这个性质对于所有点都成立。
我们可以看到二叉搜索树适用于解决求前驱后继、求排名、求第k大等问题。但是如果出题人执(sang)意(xin)要(bing)卡(kuang)，造出递减或递增的数据出来，那么你的常规二叉搜索树的每一次插入和查找都是O(n)的，会被时代淘汰的。我们只有提高自己的姿势水平才行。
splay也是一颗二叉搜索树。但是它有个优点：它可以通过旋转节点改变树的形状，江低树的直径，从而江低复杂度。从理论上看，这棵树的深度是logN的，所以一次查询的复杂度就是logN。
那么怎样进行旋转节点就是一个神奇的问题了！
我们要把节点x旋转到它的父亲y的位置，就可以找到规律：
如果x是左儿子，那么y就要变成x的右儿子，x原本的右儿子要变成y的左儿子。
如果x是右儿子，情况是差不多的。
这点东西都很好写，几个if就差不多了(所以常数很大)。关键是旋转技巧。
splay(x,goal)，表示江x旋转到goal的儿子处。
如果x是goal的孙子，那么转一次就好了。
不是的话，我们就可以把x转到它的爷爷的位置上面(因为要江低复杂度和树的直径，别问我为什么，问塔尖去)。
你还可以在旋转顺序上做点优化来达到江低直径的效果。
上题。BZOJ书架 操作还是很全的。
但其实初学者还是像我一样先做 codevs营业额统计 比较好，操作较少但splay不少。
改变位置就相当于删除再插入。求排名就是把它splay到顶端然后看左子树大小。
第k本就是第k大，就是二叉搜索树的普通操作。
书架 代码如下。num应该改名成fact，表示点对应的书的编号。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
const int N = 300010;
int n,m,T[N],ch[N][2],size[N],num[N];
int fa[N],root,tot,pos[N],rec[N];
int gi()
{
int x=0,res=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*res;
}
LL gl()
{
LL x=0,res=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*res;
}
int gsize(int x){return x?size[x]:x;}
void up(int x){size[x]=gsize(ch[x][0])+gsize(ch[x][1])+1;}
void rtt(int x,int kind) //综合版，包含了zig和zag。
{
int y=fa[x],z=fa[y];
ch[y][!kind]=ch[x][kind];fa[x]=z;
if(ch[x][kind])fa[ch[x][kind]]=y;
if(z)
if(ch[z][0]==y)ch[z][0]=x;
else ch[z][1]=x;
ch[x][kind]=y;fa[y]=x;
up(y);up(x);
}
void splay(int x,int goal)
{
if(x==goal)return;
while(fa[x]!=goal)
if(fa[fa[x]]==goal)
rtt(x,ch[fa[x]][0]==x);
else
{
int y=fa[x],kind=ch[fa[y]][0]==y;
if(ch[y][kind]==x)rtt(x,kind^1),rtt(x,kind);
else rtt(y,kind),rtt(x,kind); //听缩这样可以江低复杂度，实际上是的。
}
if(goal==0)root=x;
}
void newnode(int &r,int fat,int x)
{
r=++tot;fa[tot]=fat;size[tot]=1;
ch[tot][0]=ch[tot][1]=0;num[tot]=x;return;
}
void insert(int rt,int x,int value) //把一个编号为x的书放到位置value上
{
if(value==1 && ch[rt][0]==0){newnode(ch[rt][0],rt,x);return;}
if(value==2+gsize(ch[rt][0])&&ch[rt][1]==0){newnode(ch[rt][1],rt,x);return;}
if(value<=1+gsize(ch[rt][0]))insert(ch[rt][0],x,value);
else insert(ch[rt][1],x,value-gsize(ch[rt][0])-1);
up(x);
}
void del(int x)
{
splay(x,0);
if(ch[x][0]==0&&ch[x][1]==0){root=0;return;}
if(ch[x][0]==0){root=ch[x][1];fa[root]=0;return;}
if(ch[x][1]==0){root=ch[x][0];fa[root]=0;return;}
int tmp=ch[x][0];while(ch[tmp][1])tmp=ch[tmp][1];
splay(tmp,x);root=tmp;fa[tmp]=0;
ch[tmp][1]=ch[x][1];fa[ch[x][1]]=tmp;
up(tmp);
}
int getsize(int x){splay(x,0);return gsize(ch[x][0])+1;}
int gc()
{
char ch=getchar();
while(ch>'Z' || ch<'A')ch=getchar();
if(ch=='T')return 1;
if(ch=='B')return 2;
if(ch=='I')return 3;
if(ch=='A')return 4;
if(ch=='Q')return 5;
return 0;
}
void pr(int x)
{
printf(" point %d: ls=%d rs=%d size=%d\n",x,ch[x][0],ch[x][1],gsize(x));
if(ch[x][0])pr(ch[x][0]);if(ch[x][1])pr(ch[x][1]);
}
int find(int x)
{
int pt=x,r=root;
while(1)
{
if(pt==1+gsize(ch[r][0]))return num[r];
if(pt>1+gsize(ch[r][0]))pt-=(1+gsize(ch[r][0])),r=ch[r][1];
else r=ch[r][0];
}
return num[0];
}
int main()
{
n=gi();m=gi();
for(int i=1;i<=n;++i)
{
rec[i]=gi();
pos[rec[i]]=i;
if(i==1)newnode(root,0,rec[1]),root=tot;
else{insert(root,rec[i],i);if(i%2)splay(tot,0);}
}
for(int i=1;i<=m;++i)
{
int type=gc(),x=gi(),y=type==3?gi():0;
switch(type)
{
case 1:{del(pos[x]);insert(root,x,1);pos[x]=tot;splay(tot,0);break;}
case 2:{del(pos[x]);insert(root,x,n);pos[x]=tot;splay(tot,0);break;}
case 3:{int S=getsize(pos[x])+y;del(pos[x]);insert(root,x,S);splay(tot,0);pos[x]=tot;break;}
case 4:{printf("%d\n",getsize(pos[x])-1);break;}
case 5:{printf("%d\n",find(x));break;}
default:continue;
}
}
return 0;
}