Splay-伸展树学习笔记
本来很早以前就想钻研一下Splay树这种神奇的数据结构，只是一直没理解，一拖再拖，就在前几天的网络赛上突然遭遇了一道非Splay不可的题，看来不学是不行的了。今早再次拜读了Crash神牛的《运用伸展树解决数列维护问题》、杨思雨神牛的《伸展树的基本操作与应用》以及小HH的博客，加上网上到处乱飞的模板，终于稍有些领悟了。
Splay题目：
[HNOI2002]营业额统计 难度：**
题意：每次读入一个数，在已输入的数中找到与之差值最小的数，把它们差的绝对值累加起来最后输出。
解析：貌似是最简单的一个Splay题了吧，如果每读入一个数都在已输入的数字里面线性扫描一遍，应该TLE了。进一步地说，如果我们把数字保存成二叉排序树的形式，即每个结点如果存在左子树，则左子树上每个结点的值都比该结点的值小，如果存在右子树，则右子树上的每个结点的值都要比该结点的值大。这样每读入一个数，我们只要比较这个数在树里面的直接前驱和直接后继与这个数的差值的大小即可。使用Splay可以每次都把读入的数旋到树根以便查找（貌似建立一个二叉线索树也可）。
hdu 1890 Robotic Sort 难度：***
详见解题报告。
hdu 3487 Play with Chain 难度：***
题意：维护一段数列，有两种操作：1、截取a-b之间的数字插入到c后；2、将a-b之间的数字翻转。
解析：区间的删除插入以及翻转操作，为了方便截取，给区间添加两端点。对于第一种操作：把a前一个位置的数Splay到树根，b后一个位置的数Splay到树根的右子树。然后把树根的右子树的左子树砍下来。把c Splay到树根，后一个数字Splay到树根的右子树（可使其左子树为空），把砍下的子树接到左子树即可；对于第二种操作，同样把ab前后的数字Splay到树根和根的右子树，给根的右子树的左子树的翻转标记取反。中序遍历树即可得到答案。
void Insert(Node *p,int pos)
{
Splay(Select(pos+1),null);
Node *f=Select(pos+2);
Splay(f,root);
f->ch[0]=p;
p->pre=f;
Update(f);
}
Node* Cut(int a,int b)
{
Splay(Select(a),null);
Node *p=Select(b+2);
Splay(p,root);
Node *tmp=p->ch[0];
p->ch[0]=null;
return tmp;
}
void Flip(int a,int b)
{
Splay(Select(a),null);
Node *p=Select(b+2);
Splay(p,root);
root->ch[1]->ch[0]->rev=!root->ch[1]->ch[0]->rev;
}
spoj 4487. Can you answer these queries VI 难度：****
题意：维护序列，有四种操作：1、在指定位置插入一个数，2、删除指定位置的数，3、用一个数替换指定位置的数，4、求一段区间里的最大子段和。
解析：插入与上题的相同，至于删除，可以用上面的方法，也可以把指定位置的元素Splay到根，砍掉左右子树，把右子树里面的第一个数Splay到根，然后根的左子树接刚砍下的左子树。而替换只需把指定位置Splay到跟，直接改根的val即可。最大子段和的统计需要在每个节点添加：sum(子树和)，lsum（左子树的最大子段和）,rsum（右子树的最大子段和）,msum（该子树的最大子段和），执行前三个操作时维护好节点信息即可。
NOI2005 维修数列 难度：*****
题意：维护序列，有六种操作：插入、删除、修改、翻转、求和、求最大子段和。
解析：Crash论文里面提到的题目，论文讲得很详细了，而六种鬼畜操作在以上的题目里面都有涉及，所以就不单独写了。
献出模板：
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int IN[500010];
const int INF=1<<28;
struct Node
{
Node *pre,*ch[2];
bool rev,same;
int sz,val,sum,MaxM,MaxL,MaxR;
}*root,buf[500010],*null;
Node *stack[500010];
int idx,N,M,top;
Node *addNode(int val)
{
Node *p;
if(top)p=stack[--top];
else p=&buf[idx++];
p->rev=p->same=false;
p->sz=1;
p->sum=p->val=p->MaxM=p->MaxL=p->MaxR=val;
p->ch[0]=p->ch[1]=p->pre=null;
return p;
}
inline void PushDown(Node *p)
{
if(p==null||!p)return;
if(p->rev)
{
swap(p->ch[0],p->ch[1]);
if(p->ch[0]!=null)p->ch[0]->rev=!p->ch[0]->rev;
if(p->ch[1]!=null)p->ch[1]->rev=!p->ch[1]->rev;
swap(p->MaxL,p->MaxR);
p->rev=false;
}
if(p->same)
{
p->sum=p->sz*p->val;
p->MaxM=p->MaxL=p->MaxR=max(p->val,p->sum);
if(p->ch[0]!=null)
{
p->ch[0]->val=p->val;
p->ch[0]->same=true;
}
if(p->ch[1]!=null)
{
p->ch[1]->val=p->val;
p->ch[1]->same=true;
}
p->same=false;
}
}
inline void Update(Node *p)
{
if(p==null)return;
PushDown(p);
PushDown(p->ch[0]);
PushDown(p->ch[1]);
p->sz=p->ch[0]->sz+p->ch[1]->sz+1;
p->sum=p->val+p->ch[0]->sum+p->ch[1]->sum;
p->MaxL=max(p->ch[0]->MaxL,p->ch[0]->sum+p->val+max(0,p->ch[1]->MaxL));
p->MaxR=max(p->ch[1]->MaxR,p->ch[1]->sum+p->val+max(0,p->ch[0]->MaxR));
p->MaxM=max(max(p->ch[1]->MaxL,0)+p->val+max(p->ch[0]->MaxR,0),max(p->ch[0]->MaxM,p->ch[1]->MaxM));
}
void Init()
{
idx=top=0;
null=addNode(-INF);
null->sz=null->sum=0;
root=addNode(-INF);
root->sum=0;
Node *p;
p=addNode(-INF);
root->ch[1]=p;
p->pre=root;
p->sum=0;
Update(root->ch[1]);
Update(root);
}
void Rotate(Node *x,int c)
{
Node *y=x->pre;
PushDown(y);PushDown(x);
y->ch[!c]=x->ch[c];
if(x->ch[c]!=null)
x->ch[c]->pre=y;
x->pre=y->pre;
if(y->pre!=null)
if(y->pre->ch[0]==y)
y->pre->ch[0]=x;
else
y->pre->ch[1]=x;
x->ch[c]=y;y->pre=x;
if(y==root)root=x;
Update(y);
}
void Splay(Node *x,Node *f)
{
PushDown(x);
while(x->pre!=f)
{
Node *y=x->pre,*z=y->pre;
if(x->pre->pre==f)
Rotate(x,x->pre->ch[0]==x);
else
{
if(z->ch[0]==y)
if(y->ch[0]==x)
Rotate(y,1),Rotate(x,1);
else
Rotate(x,0),Rotate(x,1);
else
if(y->ch[1]==x)
Rotate(y,0),Rotate(x,0);
else
Rotate(x,1),Rotate(x,0);
}
}
Update(x);
}
Node* Select(int kth)
{
int tmp;
Node *t=root;
while(1)
{
PushDown(t);
tmp=t->ch[0]->sz;
if(tmp+1==kth)break;
if(kth<=tmp)
t=t->ch[0];
else
{
kth-=tmp+1;
t=t->ch[1];
}
}
return t;
}
Node * Build(int l,int r)
{
if(l>r)return null;
int mid=(l+r)>>1;
Node *p=addNode(IN[mid]);
p->ch[0]=Build(l,mid-1);
if(p->ch[0]!=null)
p->ch[0]->pre=p;
p->ch[1]=Build(mid+1,r);
if(p->ch[1]!=null)
p->ch[1]->pre=p;
Update(p);
return p;
}
void Recycle(Node *p)
{
if(p->ch[0]!=null)Recycle(p->ch[0]);
if(p->ch[1]!=null)Recycle(p->ch[1]);
stack[top++]=p;
}
void Delete(int pos,int tot)
{
Splay(Select(pos-1),null);
Splay(Select(pos+tot),root);
if(root->ch[1]->ch[0]!=null)
{
Recycle(root->ch[1]->ch[0]);
root->ch[1]->ch[0]=null;
}
Update(root->ch[1]);Update(root);
Splay(root->ch[1],null);
}
void Insert(int pos,int tot)
{
for(int i=1;i<=tot;i++)
scanf("%d",IN+i);
Node *troot=Build(1,tot);
Splay(Select(pos),null);
Splay(Select(pos+1),root);
root->ch[1]->ch[0]=troot;
troot->pre=root->ch[1];
Update(root->ch[1]);Update(root);
Splay(troot,null);
}
void Reverse(int pos,int tot)
{
Splay(Select(pos-1),null);
Splay(Select(pos+tot),root);
if(root->ch[1]->ch[0]!=null)
{
root->ch[1]->ch[0]->rev=!root->ch[1]->ch[0]->rev;
Splay(root->ch[1]->ch[0],null);
}
}
void GetSum(int pos,int tot)
{
Splay(Select(pos-1),null);
Splay(Select(pos+tot),root);
printf("%d\n",root->ch[1]->ch[0]->sum);
}
void MakeSame(int pos,int tot)
{
int c;
scanf("%d",&c);
Splay(Select(pos-1),null);
Splay(Select(pos+tot),root);
root->ch[1]->ch[0]->val=c;
root->ch[1]->ch[0]->same=true;
Splay(root->ch[1]->ch[0],null);
}
void MaxSum()
{
Splay(Select(1),null);
Splay(Select(root->sz),root);
printf("%d\n",root->ch[1]->ch[0]->MaxM);
}
void T(Node *p)
{
if(p->ch[0]!=null)T(p->ch[0]);
printf("%d ",p->val);
if(p->ch[1]!=null)T(p->ch[1]);
}
int main()
{
scanf("%d%d",&N,&M);
Init();
for(int i=1;i<=N;i++)
scanf("%d",IN+i);
Node *troot=Build(1,N);
root->ch[1]->ch[0]=troot;
troot->pre=root->ch[1];
Update(root->ch[1]);
Update(root);
while(M--)
{
char com[20];
scanf("%s",com);
int a,b;
if(com[2]!='X')
scanf("%d%d",&a,&b);
switch(com[2])
{
case 'S':Insert(a+1,b);break;
case 'L':Delete(a+1,b);break;
case 'V':Reverse(a+1,b);break;
case 'K':MakeSame(a+1,b);break;
case 'T':GetSum(a+1,b);break;
case 'X':MaxSum();break;
}
}
return 0;
}
2010年11月01日 21:33
Orz 凯神