Description 一个字符串，两个指针L和R，三种操作： S X Y：让X指针向Y方向移动一个位置，X、Y可能是L或R R：把L指针和R指针中间这一段字符串翻转，但是指针不懂 Q X：查询X指针指向的字符，X可能是L或R Input 第一行三个整数n,a,b分别表示字符串长度和初始状态两个指针的位置，然后输入一个长度为n的字符串，然后输入一个整数m表示操作数，之后m行每行一种操作(1<=n<=1e5,1<= a < b <=n,1<=m<=3e5) 保证操作过程中指针不会跑到字符串外面去 Output 对于每次查询操作，输出查询的指针指向的字符 Sample Input 11 2 6 abracadabra 12 Q L Q R R Q L Q R S L R S R R Q L Q R R Q L Q R Sample Output baabcddc Solution 维护一个双端链表，查询操作和移动操作不用多说，对于反转操作，反转这一段内部连接和原来相反了，即p->pre是p的下一个元素，p->next是p的上一个元素，所以移动的时候要注意，往反转部分走的时候，把当前这个点变“正常”，而向反转部分反向走时，要把当前走的点变“不正常”，这样就可以保证只有两个指针中间部分可能是不正常的，而不影响两端 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 111111 typedef struct node { char c; node *pre,*next; }*list; int n,a,b,m; char s[maxn]; int main() { while(~scanf("%d%d%d",&n,&a,&b)) { list head,tail,p,q,l,r; head=(list)malloc(sizeof(node)); head->pre=NULL; tail=(list)malloc(sizeof(node)); tail->next=NULL; head->next=tail,tail->pre=head; p=head; scanf("%s",s); for(int i=0;i<n;i++) { q=(list)malloc(sizeof(node)); q->c=s[i]; q->pre=p,p->next=q; p=q; if(i==a-1)l=p; if(i==b-1)r=p; } p->next=tail; scanf("%d",&m); int flag=0; while(m--) { char op[3]; scanf("%s",op); if(op[0]=='Q') { scanf("%s",op); if(op[0]=='L')printf("%c",l->c); else printf("%c",r->c); } else if(op[0]=='R') { if(!flag) { p=l->pre,q=r->next; p->next=r,r->next=p; q->pre=l,l->pre=q; p=r,r=l,l=p; } else { p=l->next,q=r->pre; p->next=r,r->pre=p; q->pre=l,l->next=q; p=r,r=l,l=p; } flag^=1; } else { scanf("%s",op); if(op[0]=='L') { scanf("%s",op); if(op[0]=='L') { if(flag) { p=l->next,q=p->pre; p->pre=l,p->next=q; l=p; } else l=l->pre; } else { if(flag) { q=l->pre,p=l->next; l->pre=p,l->next=q; l=q; } else l=l->next; } } else { scanf("%s",op); if(op[0]=='R') { if(flag) { p=r->pre,q=p->next; p->pre=q,p->next=r; r=p; } else r=r->next; } else { if(flag) { p=r->pre,q=r->next; r->next=p,r->pre=q; r=q; } else r=r->pre; } } } } printf("\n"); } return 0; }