伸展树看了几天了，总算是摸着点方向，只能说这真的是神一样的数据结构，各种延迟标记……
参考了很多大牛的博客，代码的基本写法从网上挑了一种比较好理解的开始模仿。
这里有一个模板和对一道题的分析，一开始我模仿的就是这个，最后发现指针还是有点不习惯……最后我会贴出用这个模板解这题的代码。
这个模板是少数这道题可以跑进1s内的，不过利用数组建树那部分似乎有bug：
Splay Tree 标签_51CTO技术博客
以下链接是网上关于Splay的总结，里面有许多题解……这些都给了我很大的帮助！
cxlove的，网上很多人都是他的写法修改的：伸展树（Splay tree）学习小结 - 窝是爱酱,喵~~~~ - 博客频道 - CSDN.NET
kuangbin的，我正在模仿他的写法：Splay Tree（伸展树总结） - kuangbin - 博客园
今年8月写了400多博文的 haha593572013 的：无比强大的数据结构 伸展树总结 - 鲜花会有的，AC会有的！ - 博客频道 - CSDN.NET
FZU_Jason的，还没有仔细看：【总结】伸展树 - DrunBee - 博客园
这道题的题意和分析在上面几篇博客里都有，我就不写了。
#include <cstdio>
#include <algorithm>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define Key_value ch[ch[root][1]][0] //根节点右孩子的左孩子
#define Key_Value ch[ch[root][1]][0]
const int N=200010;
const int INF=0x3f3f3f3f;
//分别表示父结点,左右孩子(0为左孩子，1为右孩子),键值,结点规模
int pre[N],ch[N][2],key[N],size[N];
//加法延迟标记,翻转延迟标记,最小值
int add[N],rev[N],m[N];
int root,tot1; //根节点,节点数量
int s[N],tot2;//内存池、内存池容量
int data[N]; //初始数列数组
int n,q;
void NewNode (int &r,int father,int k)
{
if (tot2)r=s[tot2--];
else r=++tot1;
ch[r][0]=ch[r][1]=0;
pre[r]=father;
size[r]=1;
add[r]=rev[r]=0;
key[r]=m[r]=k;
}
void Update_Rev (int r) //更新r节点的翻转值
{
if(!r)return;
swap(ch[r][0],ch[r][1]);
rev[r]^=1;
}
void Update_Add (int r,int ADD) //更新r节点的加法值
{
if(!r)return;
add[r]+=ADD;
key[r]+=ADD;
m[r]+=ADD;
}
void Push_Up (int r) //向上更新,由r节点的儿子更新r节点
{
size[r]=size[ch[r][0]]+size[ch[r][1]]+1;
m[r]=key[r];
if(ch[r][0])m[r]=min(m[r],m[ch[r][0]]);
if(ch[r][1])m[r]=min(m[r],m[ch[r][1]]);
}
void Push_Down (int r) //向下更新,由r节点更新其儿子节点
{
if (rev[r])
{
Update_Rev(ch[r][0]);
Update_Rev(ch[r][1]);
rev[r]=0;
}
if (add[r])
{
Update_Add(ch[r][0],add[r]);
Update_Add(ch[r][1],add[r]);
add[r]=0;
}
}
void Build (int &x,int l,int r,int father)
{//利用数组data建树,data从1开始,有n个元素
//调用格式 Build(Key_value,1,n,ch[root][1]);
if (l>r) return;
int mid=(l+r)>>1;
NewNode(x,father,data[mid]);
Build(ch[x][0],l,mid-1,x);
Build(ch[x][1],mid+1,r,x);
Push_Up(x);
}
void Init ()
{//Splay初始化
root=tot1=tot2=0;
ch[root][0]=ch[root][1]=size[root]=add[root]=rev[root]=pre[root]=0;
m[root]=INF;//这个不用也可以,如果在push_up那判断了的话，否则需要
NewNode(root,0,INF);
NewNode(ch[root][1],root,INF);
Push_Up(ch[root][1]);
Push_Up(root);
}
void Rotate (int x,int kind)
{//旋转
int y=pre[x];
Push_Down(y);
Push_Down(x);
ch[y][!kind]=ch[x][kind];
pre[ch[x][kind]]=y;
if(pre[y])
ch[pre[y]][ch[pre[y]][1]==y]=x;
pre[x]=pre[y];
ch[x][kind]=y;
pre[y]=x;
Push_Up(y);
}
void Splay (int r,int goal)
{//Splay调整,将第r节点调整到goal位置
Push_Down(r);
while(pre[r]!=goal)
{
if(pre[pre[r]]==goal)
{
//这题有反转操作，需要先push_down,再判断左右孩子
Push_Down(pre[r]);
Push_Down(r);
Rotate(r,ch[pre[r]][0]==r);
}
else
{
//这题有反转操作，需要先push_down,再判断左右孩子
Push_Down(pre[pre[r]]);
Push_Down(pre[r]);
Push_Down(r);
int y=pre[r];
int kind=(ch[pre[y]][0]==y);
//两个方向不同，则先左旋再右旋
if(ch[y][kind]==r)
{
Rotate(r,!kind);
Rotate(r,kind);
}
//两个方向相同，相同方向连续两次
else
{
Rotate(y,kind);
Rotate(r,kind);
}
}
}
Push_Up(r);
//更新根节点
if(goal==0)root=r;
}
int Get_Kth (int r,int k) //找第k个节点
{
Push_Down(r);
int t=size[ch[r][0]]+1;
if(t==k)return r;
if(t>k)return Get_Kth(ch[r][0],k);
else return Get_Kth(ch[r][1],k-t);
}
int Get_Min (int r)
{
Push_Down(r);
while (ch[r][0])
{
r=ch[r][0];
Push_Down(r);
}
return r;
}
int Get_Max (int r)
{
Push_Down (r);
while (ch[r][1])
{
r=ch[r][1];
Push_Down(r);
}
return r;
}
//下面是操作了
void Add (int l,int r,int D)
{//区间l到r全部加D
Splay(Get_Kth(root,l),0);
Splay(Get_Kth(root,r+2),root);
Update_Add(Key_value,D);
Push_Up(ch[root][1]);
Push_Up(root);
}
void Reverse (int l,int r)
{//区间l到r全部翻转
Splay(Get_Kth(root,l),0);
Splay(Get_Kth(root,r+2),root);
Update_Rev(Key_value);
Push_Up(ch[root][1]);
Push_Up(root);
}
void Revolve (int l,int r,int T)
{//循环右移T长度,其实就是交换区间
int len=r-l+1;
T=(T%len+len)%len;
if (T==0)return;
int c=r-T+1;//将区间[c,r]放在[l,c-1]前面
Splay(Get_Kth(root,c),0);
Splay(Get_Kth(root,r+2),root);
int tmp=Key_value;
Key_value=0; //此时已将区间拆下
Push_Up(ch[root][1]); //拆下后记得更新
Push_Up(root);
Splay(Get_Kth(root,l),0);
Splay(Get_Kth(root,l+1),root); //放在l之前
Key_value=tmp;
pre[Key_value]=ch[root][1];//这个不要忘记
Push_Up(ch[root][1]);
Push_Up(root);
}
void Insert (int x,int P)
{//在第x个数后面插入P
Splay(Get_Kth(root,x+1),0);
Splay(Get_Kth(root,x+2),root);
NewNode(Key_value,ch[root][1],P);
Push_Up(ch[root][1]);
Push_Up(root);
}
void erase (int r)
{//回收内存
if(r)
{
s[++tot2]=r;
erase(ch[r][0]);
erase(ch[r][1]);
}
}
void Delete (int x)
{//删除第x个数
Splay(Get_Kth(root,x),0);
Splay(Get_Kth(root,x+2),root);
erase(Key_value);
pre[Key_value]=0;
Key_value=0;
Push_Up(ch[root][1]);
Push_Up(root);
}
int Query_Min (int l,int r)
{//查找区间最小
Splay(Get_Kth(root,l),0);
Splay(Get_Kth(root,r+2),root);
return m[Key_value];
}
int main ()
{
#ifdef ONLINE_JUDGE
#else
freopen("read.txt","r",stdin);
#endif
int n,m,i;
char str[10];
scanf("%d",&n);
Init();
for (i=1;i<=n;i++)
scanf("%d",&data[i]);
Build(Key_value,1,n,ch[root][1]);
scanf("%d",&m);
int x,y,tmp;
while (m--)
{
scanf("%s",str);
switch (str[0])
{
case 'A':
scanf("%d%d%d", &x, &y, &tmp);
Add(x,y,tmp);
break;
case 'R':
if ('E' == str[3])
{
scanf("%d%d", &x, &y);
Reverse(x, y);
}
else
{
scanf("%d%d%d", &x, &y, &tmp);
Revolve(x, y, tmp);
}
break;
case 'I':
scanf("%d%d", &x, &tmp);
Insert(x,tmp);
break;
case 'D':
scanf("%d", &x);
Delete(x);
break;
case 'M':
scanf("%d%d", &x, &y);
printf("%d\n",Query_Min(x,y));
break;
}
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define max(a,b) ((a)>(b)?(a):(b))
#define max3(a,b,c) (max(a,max(b,c)))
#define min(a,b) ((a)<(b)?(a):(b))
#define min3(a,b,c) (min(a,min(b,c)))
using namespace std;
const int INF=0x7fffffff;
const int MAXPT=1000005;
class SPLAYTREE
{
public:
struct Node
{
int key,minv,size,add;//键值,区间最小值,子树规模,相加延迟标记
bool rev; //翻转标记
Node *left,*right,*father;
Node (){}
Node(int _key):key(_key){minv=_key,size=1,add=0,rev=false;}
}SPLAY[MAXPT],*SP,*root,*head,*tail;
void init () //初始化一棵伸展树，只有head和tail结点
{//tail.size=1,head.size=1(初始)而且保证以后接入的结点：Node.size>=head.size
SP=SPLAY;
SPLAY->key=SPLAY->minv=INF,SPLAY->size=0;SPLAY->rev=false;SPLAY->add=0;
SPLAY->left=SPLAY->right=SPLAY->father=SPLAY;
head=new(++SP)Node(INF);
head->left=head->right=head->father=SPLAY;
tail=new(++SP)Node(INF);
tail->left=tail->right=tail->father=SPLAY;
head->right=tail,tail->father=head,head->size++;
root=head;//最开始,root的值为head,head和tail是固定不变的,而root的指向的地址是会变化的
}
void pushdown (Node *&t)//延迟操作的经典代码：把当前的标记下推一个节点
{
if (t->rev)
{//如果区间需要旋转
swap(t->left,t->right);
t->left->rev=!t->left->rev;
t->right->rev=!t->right->rev;
t->rev=false;
}
if (t->add)
{//如果区间的值要加add
if(t->left!=SPLAY){
t->left->key+=t->add;
t->left->minv+=t->add;
t->left->add+=t->add;
}
if(t->right!=SPLAY){
t->right->key+=t->add;
t->right->minv+=t->add;
t->right->add+=t->add;
}
t->add=0;
}
}
void pushup (Node *&t)//更新区间的最小值和区间元素的个数
{
t->size=t->left->size+t->right->size+1;
t->minv=min3(t->key,t->left->minv,t->right->minv);
}
void zig (Node *&t)
{ //右旋转操作
Node *f=t->father,*r=t->right;
pushdown(f->right);
pushdown(t->left);
pushdown(t->right);
t->father=f->father;
if (f==root) root=t;
else{
if(f->father->left==f) f->father->left=t;
else f->father->right=t;
}
t->right=f,r->father=f,f->father=t,f->left=r;
pushup(f);pushup(t);
}
void zag (Node *&t)
{ //左旋转操作
Node *f=t->father,*l=t->left;
pushdown(f->left);
pushdown(t->left);
pushdown(t->right);
t->father=f->father;
if(f==root) root=t;
else{
if(f->father->left==f) f->father->left=t;
else f->father->right=t;
}
t->left=f,l->father=f,f->father=t,f->right=l;
pushup(f);pushup(t);
}
void splay (Node *&root,Node *&t)
{// 伸展树的核心：伸展操作
pushdown(t);
while (root!=t)
{
if(t->father==root){
if(t->father->left==t) zig(t);
else zag(t);//单旋转
}
else{
if(t->father->father->left==t->father){
if(t->father->left==t) zig(t->father),zig(t);//一字旋转
else zag(t),zig(t);//之字旋转
}else{
if(t->father->left==t) zig(t),zag(t);//之字旋转
else zag(t->father),zag(t);//一字旋转
}
}
}
}
// 建树 /
Node* build (Node *father,int *a,int ll,int rr) //返回该树根节点
{ //仿线段树建树方式建立一个splay树，与build_tree合用
if(ll>rr)return SPLAY;
int mid=(ll+rr)>>1;
SP=SP+mid;
Node *t;
t=new(SP)Node(a[mid]);
t->father=father;
t->left=build(t,a,ll,mid-1);
t->right=build(t,a,mid+1,rr);
pushup(t);
return t;
}
/*
* function: 把数组a建立成一棵伸展树。采用的建树方式与线段树的建树方式相同
*
* @param:root 新建立树的根
* @param: a 建树用到的数组，0位置不存元素
* @param: n 数组a中元素的个数
* */
void build_tree (Node *&t,int *a,int n)
{
int ll=1,rr=n;
int mid=(ll+rr)>>1;
SP=SP+mid;
t=new(SP)Node(a[mid]);
t->father=SPLAY;
t->left=build(t,a,ll,mid-1);
t->right=build(t,a,mid+1,rr);
pushup(t);
}
void insert (int key,int pos)
{// 插入一个值到指定的位置
Node *t=new(++SP)Node(key);
t->left=t->right=t->father=SPLAY;
Node *r=root,*p;
bool flag=false;//默认插入树的左孩子上
while(pushdown(r),r!=SPLAY){
p=r,r->size++;
if(r->left->size+1>pos)r=r->left,flag=false;
else pos-=r->left->size+1,r=r->right,flag=true;
}
if(flag) p->right=t;
else p->left=t;
t->father=p;
splay(root,t);
}
// 建树 /
void select (Node *&root,int pos)
{// 把pos位置的元素旋转到根结点(或任意*&root所指的位置)
Node *r=root;
while (pushdown(r),r->left->size+1!=pos){
if(r->left->size+1>pos) r=r->left;
else pos-=r->left->size+1,r=r->right;
}
splay(root,r);
}
void insert_k (int pos,int *a,int n) //函数有bug!!!!!!!
{ //把a中的n个数插入数组中，a的0号位不用
Node *t;
build_tree(t,a,n);
select(root,pos);
select(root->right,1);
root->right->left=t;
t->father=root->right;
pushup(root->right);
pushup(root);
splay(root,t);
}
void remove (int pos)
{// 把pos位置的元素删除
select(root,pos);
if(root->left==SPLAY) root=root->right;
else if(root->right==SPLAY) root=root->left;
else{
select(root->left,root->left->size);
root->left->right=root->right;
root->right->father=root->left;
root=root->left;
}
root->father=SPLAY;
pushup(root);
}
void remove_k (int ll,int rr)
{ //删除区间[l,r]
//确定区间
select(root,ll);
select(root->right,rr-ll);
//执行删除操作
root->right->left=SPLAY;
pushup(root->right);
pushup(root);
}
void plus (int l,int r,int a)
{//区间[l,r]同时加上a
//确定区间
select(root,l);
select(root->right,r-l);
//执行操作
Node *t=root->right->left;
t->add+=a,t->key+=a,t->minv+=a;
splay(root,t); //记得splay
}
void reverse (int l,int r)
{// 翻转区间[l,r]
select(root,l);
select(root->right,r-l);
Node *t=root->right->left;
t->rev=!t->rev;
splay(root,t); //记得splay
}
void revolve (int l,int r,int a)
{// 区间[l,r]循环右移a次,revolve l r a 其实就是交换(l,r-a)和(r-a+1,r)两个区间。
if (a%(r-2-l+1)) //传递过来的参数与带求差2
{
a=a%(r-2-l+1);
select(root,l);
select(root->right,r-l);
select(root->right->left,root->right->left->size-a);
select(root->right->left->right,root->right->left->right->size);
Node *p=root->right->left,*t=root->right->left->right;
p->right=SPLAY;
p->father->left=t,t->father=p->father;
t->right=p,p->father=t;
pushup(t);pushup(p);
splay(root,p); //} //记得splay
}
}
int query (int l,int r)
{ //查询区间的最小值
select(root,l);
select(root->right,r-l);
return root->right->left->minv;
}
void inorder (Node *t)
{ //从结点t开始 中序遍历树
pushdown(t);
if (t->left!=SPLAY)
inorder(t->left);
if (t->key!=INF)printf("%d ",t->key);
if (t->right!=SPLAY)
inorder(t->right);
}
}tree;
int l,r,x,pos;
char str[10];
int data[100000+10];
int main ()
{
#ifdef ONLINE_JUDGE
#else
freopen("read.txt","r",stdin);
#endif
int n,m,i;
scanf("%d",&n);
tree.init();
for (i=1;i<=n;i++)
scanf("%d",&data[i]);//,tree.insert(data[i],i);
tree.insert_k(1,data,n);
scanf("%d",&m);
int x,y,tmp;
while (m--)
{
scanf("%s",str);
switch (str[0])
{
case 'A':
scanf("%d%d%d", &x, &y, &tmp);
y+=2;
tree.plus(x,y,tmp);
break;
case 'R':
if ('E' == str[3])
{
scanf("%d%d", &x, &y); x,y+=2;
tree.reverse(x, y);
}
else
{
scanf("%d%d%d", &x, &y, &tmp); x,y+=2;
tree.revolve(x, y, tmp);
}
break;
case 'I':
scanf("%d%d", &x, &tmp); x++;
tree.insert(tmp,x);
break;
case 'D':
scanf("%d", &x); x++;
tree.remove(x);
break;
case 'M':
scanf("%d%d", &x, &y); x,y+=2;
int ans=tree.query(x, y);
printf("%d\n",ans);
break;
}
}
return 0;
}更多推荐
Splay伸展树学习小记 Poj 3580 SuperMemo
发布评论