POJ 3580 SuperMemo (Splay tree)
転載は出典を明記してください.ありがとうございます. http://blog.csdn.net/ACM_cxlove?view mode=contensts by---cxlove
とてもBTのデータ構造の問題でもあります.
操作が多いです.特有の動作の1つは、REVOLVE右シフト動作である.区間[a,b]をcビット右にシフト
まずcが多いかもしれませんが、区間長を先に型取りすることができます.
右シフト後,[a,b]は2つの区間[a,b−c]に分かれていることが分かった. [b-c+1,b]後者を前者の前に挿入すればよい.
INSERTとDELETEの操作に変えることができて、メモリはきつくて、手動のメモリプールを使って、動的なSPLAYは時間の上で多くなることができて、あまり書くことに慣れません.
とてもBTのデータ構造の問題でもあります.
操作が多いです.特有の動作の1つは、REVOLVE右シフト動作である.区間[a,b]をcビット右にシフト
まずcが多いかもしれませんが、区間長を先に型取りすることができます.
右シフト後,[a,b]は2つの区間[a,b−c]に分かれていることが分かった. [b-c+1,b]後者を前者の前に挿入すればよい.
INSERTとDELETEの操作に変えることができて、メモリはきつくて、手動のメモリプールを使って、動的なSPLAYは時間の上で多くなることができて、あまり書くことに慣れません.
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<algorithm>
#define N 200005
#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,a[N];
int size[N],pre[N],rev[N],val[N],same[N],add[N],m[N];
int ch[N][2],tot1,root,s[N],tot2;
//debug copy from hh
void Treaval(int x) {
if(x) {
Treaval(ch[x][0]);
printf(" %2d: %2d %2d %2d size = %2d ,val = %2d min =%2d
",x,ch[x][0],ch[x][1],pre[x],size[x],val[x],m[x]);
Treaval(ch[x][1]);
}
}
void debug() {printf("%d
",root);Treaval(root);}
// Debug
void Update_Rev(int r){
if(!r) return;
swap(ch[r][0],ch[r][1]);
rev[r]^=1;
}
void Update_Add(int r,int ADD){
if(!r) return;
m[r]+=ADD;
val[r]+=ADD;
add[r]+=ADD;
}
void NewNode(int &r,int k,int father){
if(tot2)
r=s[tot2--];
else
r=++tot1;
ch[r][0]=ch[r][1]=0;
pre[r]=father;
val[r]=m[r]=k;
size[r]=1;
add[r]=0;
}
void Push_Up(int x){
int l=ch[x][0],r=ch[x][1];
size[x]=size[l]+size[r]+1;
m[x]=min(min(m[l],m[r]),val[x]);
}
void Push_Down(int x){
int l=ch[x][0],r=ch[x][1];
if(add[x]){
Update_Add(l,add[x]);
Update_Add(r,add[x]);
add[x]=0;
}
if(rev[x]){
Update_Rev(l);
Update_Rev(r);
rev[x]=0;
}
}
void Bulid(int &r,int L,int R,int father){
if(L>R)
return ;
int mid=(L+R)/2;
NewNode(r,a[mid],father);
Bulid(ch[r][0],L,mid-1,r);
Bulid(ch[r][1],mid+1,R,r);
Push_Up(r);
}
void Init(){
tot1=tot2=root=0;
ch[root][0]=ch[root][1]=pre[root]=rev[root]=size[root]=add[root]=0;
m[root]=inf;
NewNode(root,inf,0);
NewNode(ch[root][1],inf,root);
Push_Up(root);
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;
}
void RotateTo(int k,int goal) {
int r=root;
Push_Down(r);
while(size[ch[r][0]]!=k){
if(k<size[ch[r][0]]){
r=ch[r][0];
} else {
k-=(size[ch[r][0]]+1);
r=ch[r][1];
}
Push_Down(r);
}
Splay(r,goal);
}
int Get_Kth(int r,int 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 Reversal(int l,int r){
int x=Get_Kth(root,l);
Splay(x,0);
int y=Get_Kth(root,r+2);
Splay(y,root);
Update_Rev(Key_value);
}
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);
}
int cnt;
void InOrder(int r){
if(r==0)
return;
Push_Down(r);
InOrder(ch[r][0]);
if(cnt>=1)
printf("%d ",val[r]);
cnt++;
InOrder(ch[r][1]);
}
void Insert(int pos,int k){
int x=Get_Kth(root,pos);
Splay(x,0);
int y=Get_Min(ch[root][1]);
Splay(y,root);
NewNode(Key_value,k,ch[root][1]);
Push_Up(ch[root][1]);
Push_Up(root);
}
void erase(int r){
if(!r) return;
s[++tot2]=r;
erase(ch[r][0]);
erase(ch[r][1]);
}
void Delete(int l){
int x=Get_Kth(root,l);
Splay(x,0);
int y=Get_Kth(root,l+2);
Splay(y,root);
erase(Key_value);
pre[Key_value]=0;
Key_value=0;
Push_Up(ch[root][1]);
Push_Up(root);
}
void ADD(int l,int r,int k){
int x=Get_Kth(root,l);
Splay(x,0);
int y=Get_Kth(root,r+2);
Splay(y,root);
Update_Add(Key_value,k);
Push_Up(ch[root][1]);
Push_Up(root);
}
int Get_Answer(int l,int r){
int x=Get_Kth(root,l);
Splay(x,0);
int y=Get_Kth(root,r+2);
Splay(y,root);
return m[Key_value];
}
void Revolve(int a,int b,int t){
if(!t)
return;
int c=b-t;
int x=Get_Kth(root,a);
Splay(x,0);
x=Get_Kth(root,c+2);
Splay(x,root);
//
int tmp=Key_value;
Key_value=0;
Push_Up(ch[root][1]);
Push_Up(root);
Splay(Get_Kth(root,b-c+a),0);
Splay(Get_Kth(root,b-c+a+1),root);
//
Key_value=tmp;
pre[Key_value]=ch[root][1];
//
Push_Up(ch[root][1]);
Push_Up(root);
}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&q);
Init();
char str[10];
int l,r,k;
while(q--){
scanf("%s",str);
if(!strcmp(str,"ADD")){
scanf("%d%d%d",&l,&r,&k);
ADD(l,r,k);
}
else if(!strcmp(str,"REVERSE")){
scanf("%d%d",&l,&r);
Reversal(l,r);
}
else if(!strcmp(str,"REVOLVE")){
scanf("%d%d%d",&l,&r,&k);
Revolve(l,r,(k%(r-l+1)+(r-l+1))%(r-l+1));
}
else if(!strcmp(str,"INSERT")){
scanf("%d%d",&l,&k);
Insert(l+1,k);
}
else if(!strcmp(str,"DELETE")){
scanf("%d",&l);
Delete(l);
}
else{
scanf("%d%d",&l,&r);
printf("%d
",Get_Answer(l,r));
}
}
}
return 0;
}