裸的Splay模版题,维护线段的区间加,区间翻转,插入和删除…..
LooploopTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1458Accepted Submission(s): 454
Problem Description
XXX gets a new toy named Looploop. The toy has N elements arranged in a loop, an arrow pointing to one of the elements, and two preset parameters k1 and k2. Every element has a number on it.
The figure above shows a Looploop of 6 elments. Let’s assuming the preset parameter k1 is 3, and k2 is 4.XXX can do six operations with the toy.1: add xStarting from the arrow pointed element, add x to the number on the clockwise first k2 elements.
2: reverseStarting from the arrow pointed element, reverse the first k1 clockwise elements.
3: insert xInsert a new element with number x to the right (along clockwise) of the arrow pointed element.
4: deleteDelete the element the arrow pointed and then move the arrow to the right element.
5: move xx can only be 1 or 2. If x = 1 , move the arrow to the left(along the counterclockwise) element, if x = 2 move the arrow to the right element.
6: queryOutput the number on the arrow pointed element in one line.
XXX wants to give answers to every query in a serial of operations.
Input
There are multiple test cases.For each test case the first line contains N,M,k1,k2(2≤k1<k2≤N≤105, M≤105) indicating the initial number of elements, the total number of operations XXX will do and the two preset parameters of the toy.Second line contains N integers ai(-104≤ai≤104) representing the N numbers on the elements in Looploop along clockwise direction. The arrow points to first element in input at the beginning.Then m lines follow, each line contains one of the six operations described above.It is guaranteed that the "x" in the "add","insert" and "move" operations is always integer and its absolute value ≤104. The number of elements will never be less than N during the operations.The input ends with a line of 0 0 0 0.
Output
For each test case, output case number in the first line(formatted as the sample output). Then for each query in the case, output the number on the arrow pointed element in a single line.
Sample Input
5 1 2 43 4 5 6 7query5 13 2 41 2 3 4 5move 2queryinsert 8reversequeryadd 2querymove 1querymove 1querydeletequery0 0 0 0
Sample Output
Case #1:3Case #2:2810151
Source
/* ***********************************************Author:CKbossCreated Time :2015年08月27日 星期四 09时26分05秒File Name:HDOJ4453.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;const int maxn=220000;const int INF=0x3f3f3f3f;#define Key_Value ch[ch[root][1]][0]int a[maxn],n,m,K1,K2;int ch[maxn][2],rev[maxn],add[maxn],sz[maxn],pre[maxn],key[maxn];int root,tot1;int s[maxn],tot2;void NewNode(int& x,int father,int k){if(tot2) x=s[tot2–];else x=++tot1;ch[x][0]=ch[x][1]=rev[x]=add[x]=0;sz[x]=1; pre[x]=father; key[x]=k;}void Erase(int r){if(r){s[++tot2]=r;Erase(ch[r][0]);Erase(ch[r][1]);}}void Upd_Rev(int x){if(!x) return ;swap(ch[x][0],ch[x][1]);rev[x]^=1;}void Upd_Add(int x,int d){if(!x) return ;key[x]+=d; add[x]+=d;}void Push_Up(int x) { sz[x]=sz[ch[x][1]]+sz[ch[x][0]]+1;} void Push_Down(int x){if(rev[x]){Upd_Rev(ch[x][0]); Upd_Rev(ch[x][1]);rev[x]=0;}if(add[x]){Upd_Add(ch[x][0],add[x]); Upd_Add(ch[x][1],add[x]);add[x]=0;}}void Build(int &x,int l,int r,int fa){if(l>r) return;int mid=(l+r)/2;NewNode(x,fa,a[mid]);Build(ch[x][0],l,mid-1,x);Build(ch[x][1],mid+1,r,x);Push_Up(x);}void Init(){root=tot1=tot2=0;ch[root][0]=ch[root][1]=pre[root]=sz[root]=0;NewNode(root,0,INF);NewNode(ch[root][1],root,INF);Build(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];pre[y]=x;ch[x][kind]=y;Push_Up(y);}void Splay(int r,int goal){Push_Down(r);while(pre[r]!=goal){if(pre[pre[r]]==goal){Push_Down(pre[r]);Push_Down(r);Rotate(r,ch[pre[r]][0]==r);}else{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);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=sz[ch[r][0]]+1;if(k==t) return r;if(t<k) return Get_Kth(ch[r][1],k-t);else return Get_Kth(ch[r][0],k);}void ADD(int l,int r,int d){Splay(Get_Kth(root,l),0);Splay(Get_Kth(root,r+2),root);Upd_Add(Key_Value,d);Push_Up(ch[root][1]);Push_Up(root);}void REVERSE(int l,int r){Splay(Get_Kth(root,l),0);Splay(Get_Kth(root,r+2),root);Upd_Rev(Key_Value);Push_Up(ch[root][1]);Push_Up(root);}void DELETE(int p){Splay(Get_Kth(root,p),0);Splay(Get_Kth(root,p+2),root);Erase(Key_Value);pre[Key_Value]=0;Key_Value=0;Push_Up(ch[root][1]);Push_Up(root);}void INSERT(int p,int v){Splay(Get_Kth(root,p+1),0);Splay(Get_Kth(root,p+2),root);NewNode(Key_Value,ch[root][1],v);Push_Up(ch[root][1]);Push_Up(root);}/*****************DEBUG*********************/void SHOW(int x){Push_Down(x);if(ch[x][0]) SHOW(ch[x][0]);printf("x: %d size: %d pre: %d left: %d right: %d key: %d\n",x,sz[x],pre[x],ch[x][0],ch[x][1],key[x]);if(ch[x][1]) SHOW(ch[x][1]);}void DEBUG(){cout<<"……….debug………….."<<endl;SHOW(root);}char cmd[20];int x;int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int cas=1;while(scanf("%d%d%d%d",&n,&m,&K1,&K2)!=EOF){if(n==0&&m==0&&K1==0&&K2==0) break;for(int i=1;i<=n;i++) scanf("%d",a+i);Init();printf("Case #%d:\n",cas++);while(m–){scanf("%s",cmd);if(strcmp("query",cmd)==0){Splay(Get_Kth(root,1),0);Splay(Get_Kth(root,3),root);printf("%d\n",key[Key_Value]);}else if(strcmp("move",cmd)==0){scanf("%d",&x);if(x==1){Splay(Get_Kth(root,n),0);Splay(Get_Kth(root,2+n),root);int NB=key[Key_Value];DELETE(n);INSERT(0,NB);}else if(x==2){Splay(Get_Kth(root,1),0);Splay(Get_Kth(root,3),root);int NB = key[Key_Value];DELETE(1);INSERT(n-1,NB);}}else if(strcmp("reverse",cmd)==0){REVERSE(1,K1);}else if(strcmp("insert",cmd)==0){scanf("%d",&x);INSERT(1,x);n++;}else if(strcmp("delete",cmd)==0){DELETE(1);n–;}else if(strcmp("add",cmd)==0){scanf("%d",&x);ADD(1,K2,x);}//DEBUG();}}return 0;}
版权声明：来自: 码代码的猿猿的AC之路
，我诚恳地希望能够获得你的原谅。只是你懂得的，对于有一些委屈，
