学步园

题目地址：  http://acm.hdu.edu.cn/showproblem.php?pid=4286

一道比较恶心的模拟。。。

各种操作，考虑的地方很繁琐。。。

比赛时以为是线段树，所以没敲。。。

最后半小时，才想到链表。。。

于是开始敲，直到比赛结束，还差十几行才敲完~~~~

不过，即使比赛时敲完，能不能AC还是个问题，因为后来修改代码，花了我半天多时间~~、、、

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

#define LEFT(x) (p[(x)].v&1)
#define RIGHT(x) ((p[(x)].v+1)&1)

struct Node{
	int v,s,e;
	int nx[2];
}p[1010000],tmp1,tmp2;

int n,tol;
int L,R;

void add(int l,int r,int s){
	p[tol].s=s;
	p[tol].v=0;
	p[tol].e=0;
	p[tol].nx[0]=l;
	p[tol].nx[1]=r;
	tol++;
}

void ouput(){
	int y,tmp,x=1;
	do{
		y=p[x].nx[RIGHT(x)];
		if(y!=R){
			p[y].v+=p[x].e;
			p[y].e+=p[x].e;
			p[x].e=0;
		}
		else{
			p[y].e=0;
			p[x].e=0;
		}
	//	printf("y:%d  v:%d [%d,%d] ",y,p[y].v,p[y].nx[LEFT(y)],p[y].nx[RIGHT(y)]);
		printf("%d",p[y].s);
	//	puts("");
		if(p[y].nx[RIGHT(y)]==n+2) break;
		putchar(' ');
		x=y;
	}while(1);
	puts("");
}

int main(){
	int i,t,s,x,y,z,m;
	char str[20];
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		tol=1;
		add(-1,2,0);
		for(i=1;i<=n;i++){
			scanf("%d",&s);
			add(i,i+2,s);
		}
		add(n+1,-1,0);
		scanf("%d%d",&L,&R);
		R+=2;
		scanf("%d",&m);
		while(m--){
			scanf("%s",str);
			if(strcmp(str,"MoveLeft")==0){
				scanf("%s",str);
				if(str[0]=='L'){
					x=L;
					L=p[L].nx[LEFT(L)];
					p[x].v-=p[x].e;
					p[L].e=p[x].e;
					p[x].e=0;
				}
				else{
					y=p[R].e;
					p[R].e=0;
					R=p[R].nx[LEFT(R)];
					p[R].v+=y;
					p[R].e=y;
				}
			}
			else if(strcmp(str,"MoveRight")==0){
				scanf("%s",str);
				if(str[0]=='L'){
					y=p[L].nx[RIGHT(L)];
					p[y].e=p[L].e;
					p[y].v+=p[L].e;
					p[L].e=0;
					L=y;
				}
				else{
					x=R;
					R=p[R].nx[RIGHT(R)];	
					p[x].v-=p[x].e;
					p[R].e=p[x].e;
					p[x].e=0;
				}
			}
			else if(strcmp(str,"Insert")==0){
				scanf("%s",str);
				scanf("%d",&x);
				if(str[0]=='L'){
					p[p[L].nx[RIGHT(L)]].nx[(p[p[L].nx[RIGHT(L)]].v+p[L].e)&1]=tol;
					if(p[L].e&1)
						add(p[L].nx[RIGHT(L)],L,x);
					else 
						add(L,p[L].nx[RIGHT(L)],x);
					p[L].nx[RIGHT(L)]=tol-1; 
				}
				else{
					p[p[R].nx[LEFT(R)]].nx[(p[p[R].nx[LEFT(R)]].v+p[R].e+1)&1]=tol;
					if(p[R].e&1)
						add(R,p[R].nx[LEFT(R)],x);
					else 
						add(p[R].nx[LEFT(R)],R,x);
					p[R].nx[LEFT(R)]=tol-1;
				}
			}
			else if(strcmp(str,"Delete")==0){
				scanf("%s",str);
				if(str[0]=='L'){
					x=p[L].nx[RIGHT(L)];
					p[x].v+=p[L].e;
					y=p[x].nx[RIGHT(x)];
					p[L].nx[RIGHT(L)]=y;
					p[y].nx[(p[y].v+p[L].e)&1]=L;
				}
				else{
					x=p[R].nx[LEFT(R)];
					p[x].v+=p[R].e;
					y=p[x].nx[LEFT(x)];
					p[R].nx[LEFT(R)]=y;
					p[y].nx[(p[y].v+p[L].e+1)&1]=R;
				}
			}
			else if(strcmp(str,"Reverse")==0){
				y=p[L].nx[RIGHT(L)];
				z=p[R].nx[LEFT(R)];
				p[L].nx[RIGHT(L)]=z;
				p[R].nx[LEFT(R)]=y;
				p[y].nx[(p[y].v+p[L].e)&1]=R;
				p[z].nx[(p[z].v+p[R].e+1)&1]=L;
				p[L].e++;
				p[R].e++;
			}
		//	ouput();
		}
		ouput();
	}
	return 0;
}