这题比较容易想到的做法是splay，但是splay写起来比较麻烦而且每次操作都有LogN的复杂度，双向链表也是可以实现的，但实践起来比较麻烦，尤其是翻转操作。。。
可以发现每次L或者R都是移动一位的，我们可以用更简单的数据结构来实现，用两个栈分别存L左边和R右边的数据，L和R中间的数据使用一个双端队列来保存，因为涉及到翻转操作，要用一个dir来表示当前的双端队列哪边是头哪边是尾。。。
对于题目中给出的七种操作，都可以在O(1)的复杂度内实现，为了描述方便，左栈代表L左边数的栈，右栈代表R右边数的栈。
1，MoveLeft L/R 左移左指针就是把左栈中栈顶的数弹到双端队列头部，左移右指针就是把队列尾部的元素放到右栈中。
2，MoveRight L/R 右移左指针就是把队列头部元素放到左栈中，右移右指针就是把右栈顶元素弹到双端队列尾部。
3，Insert L X 插入到队列头。
4，Insert R X 插入到队列尾。
5，Delete L 删除队列头元素。
6，Delete R 删除队列尾元素。
7，Reverse dir^=1。
1 #include <stdio.h> 2 #include <string.h> 3 #define MAXN 1000005 4 int cas,n,m,x[MAXN],l,r,tu; 5 int stkl[MAXN],stkr[MAXN],topl,topr; 6 int dq[MAXN*2],front,rear; 7 struct list_q{ 8 int dir; 9 void init(int l,int r,int n,int *x){ 10 dir=0,topl=topr=0,front=MAXN,rear=MAXN-1; 11 for(int i=1;i<l;i++)stkl[++topl]=x[i]; 12 for(int i=l;i<=r;i++)dq[++rear]=x[i]; 13 for(int i=n;i>r;i--)stkr[++topr]=x[i]; 14 } 15 void moveLR(char d,char p){ 16 if(d=='L'&&p=='L')dq[dir?++rear:--front]=stkl[topl--]; 17 else if(d=='L'&&p=='R')stkr[++topr]=dq[dir?front++:rear--]; 18 else if(d=='R'&&p=='L')stkl[++topl]=dq[dir?rear--:front++]; 19 else if(d=='R'&&p=='R')dq[dir?--front:++rear]=stkr[topr--]; 20 } 21 void insert(char p,int v){ 22 if(dir==0&&p=='R'||dir==1&&p=='L')dq[++rear]=v; 23 else dq[--front]=v; 24 } 25 void delet(char &p){ 26 if(dir==0&&p=='R'||dir==1&&p=='L')rear--; 27 else front++; 28 } 29 void reverse(){dir^=1;} 30 void outans(int *x){ 31 int p=0; 32 for(int i=1;i<=topl;i++)x[++p]=stkl[i]; 33 for(int i=front;i<=rear;i++)x[++p]=dir?dq[rear-i+front]:dq[i]; 34 for(int i=topr;i>0;i--)x[++p]=stkr[i]; 35 for(int i=1;i<p;i++)printf("%d ",x[i]);printf("%d\n",x[p]); 36 } 37 }; 38 char s1[15],s2[15]; 39 int main(){ 40 //freopen("test.in","r",stdin); 41 scanf("%d",&cas); 42 while(cas--){ 43 list_q qq; 44 scanf("%d",&n); 45 for(int i=1;i<=n;i++)scanf("%d",&x[i]); 46 scanf("%d%d%d",&l,&r,&m); 47 qq.init(l,r,n,x); 48 for(int i=1;i<=m;i++){ 49 scanf("%s",s1); 50 if(s1[0]!='R')scanf("%s",s2); 51 if(s1[0]=='I')scanf("%d",&tu); 52 switch(s1[0]){ 53 case 'M':qq.moveLR(s1[4],s2[0]);break; 54 case 'I':qq.insert(s2[0],tu);break; 55 case 'D':qq.delet(s2[0]);break; 56 case 'R':qq.reverse();break; 57 } 58 } 59 qq.outans(x); 60 } 61 return 0; 62 }