HDU 3487 Play with Chain (Splay tree)
再撸一发Splay。
包括区间切割和反转操作。
对于Splay处理区间[l,r]，将l-1转至根部，将r+1转至根的右孩子，这样根的右孩子的左子树便为[l,r]，相当犀利啊，Splay的操作大多基于这样的旋转操作。
对于切割，便是旋转之后，把子树先取下，然后再转到要插入的位置，将子树接上。
反转操作，加个懒惰标记，表示子树是否要交换，
[cpp]
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<algorithm>
#define N 300015
#define inf 1<<29
#define MOD 100000007
#define LL long long
#define Key_value ch[ch[root][1]][0]
#define _match(a,b) ((a)==(b))
using namespace std;
int n,q;
int size[N],pre[N],key[N],num[N],rev[N];
int ch[N][2],tot,root,node[N];
//debug部分copy from hh
void Treaval(int x) {
if(x) {
Treaval(ch[x][0]);
printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,key = %2d /n",x,ch[x][0],ch[x][1],pre[x],size[x],key[x]);
Treaval(ch[x][1]);
}
}
void debug() {printf("%d/n",root);Treaval(root);}
//以上Debug
void NewNode(int &r,int k,int father){
r=++tot;
ch[r][0]=ch[r][1]=0;
pre[r]=father;
rev[r]=0;
key[r]=k;
}
void Push_Up(int r){
size[r]=size[ch[r][0]]+size[ch[r][1]]+1;
}
void Push_Down(int r){
if(rev[r]){
swap(ch[r][0],ch[r][1]);
rev[ch[r][0]]^=1;
rev[ch[r][1]]^=1;
rev[r]=0;
}
}
void Bulid(int &r,int L,int R,int father){
if(L>R)
return ;
int mid=(L+R)/2;
NewNode(r,mid,father);
Bulid(ch[r][0],L,mid-1,r);
Bulid(ch[r][1],mid+1,R,r);
Push_Up(r);
}
void Init(){
tot=root=0;
ch[root][0]=ch[root][1]=pre[root]=rev[root]=size[root]=0;
NewNode(root,-1,0);
NewNode(ch[root][1],-1,root);
size[root]=2;
Bulid(Key_value,1,n,ch[root][1]);
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){
Push_Down(r);
while(pre[r]!=goal){
if(pre[pre[r]]==goal)
Rotate(r,ch[pre[r]][0]==r);
else{
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){
Push_Down(r);
int t=size[ch[r][0]];
if(t==k-1)
return r;
if(t>=k)
return Get_Kth(ch[r][0],k);
else
return Get_Kth(ch[r][1],k-t-1);
}
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 Reversal(int a,int b){
int x=Get_Kth(root,a);
int y=Get_Kth(root,b+2);
Splay(x,0);
Splay(y,root);
rev[Key_value]^=1;
}
void Cut(int a,int b,int c){
int x=Get_Kth(root,a);
int y=Get_Kth(root,b+2);
Splay(x,0);
Splay(y,root);
int tmp=Key_value;
Key_value=0;
Push_Up(ch[root][1]);
Push_Up(root);
int z=Get_Kth(root,c+1);
Splay(z,0);
int m=Get_Min(ch[root][1]);
Splay(m,root);
Key_value=tmp;
pre[Key_value]=ch[root][1];
Push_Up(ch[root][1]);
Push_Up(root);
} www.2cto.com
int cnt;
void InOrder(int r){
if(r==0)
return;
Push_Down(r);
InOrder(ch[r][0]);
if(cnt>=1&&cnt<=n){
if(cnt>1) printf(" ");
printf("%d",key[r]);
}
cnt++;
InOrder(ch[r][1]);
}
int main(){
while(scanf("%d%d",&n,&q)!=EOF){
if(n==-1&&q==-1)
break;
Init();
while(q--){
char str[10];
int a,b,c;
scanf("%s",str);
if(str[0]=='C'){
scanf("%d%d%d",&a,&b,&c);
Cut(a,b,c);
}
else{
scanf("%d%d",&a,&b);
Reversal(a,b);
}
}
cnt=0;
InOrder(root);
printf("/n");
}
return 0;
}
作者：ACM_cxlove
