你有一些小球，从左到右依次编号为1，2，3，…，n，
你可以执行两种指令。其中A X Y表示把小球X移动到小球Y左边，B X Y表示把小球X移动到小球Y右边。指令保证合法，即X不等于Y。
输入 小球个数n。指令条数m和m条指令，注意，1≤n≤500000，0≤m≤100000。
输出 从左到右输出最后的小球序列。
样例输入
6 2
A 1 4
B 3 5
样例输出
2 1 4 5 3 6
两种方法
代码1：
#include<stdio.h> const int MAXN=500000+10; int n,A[MAXN]; int find(int x) { for(int i=1;i<=n;i++) if(A[i]==x) return i; return 0; } void shift_circular_left(int a,int b) { int t=A[a]; for(int i=a;i<b;i++) A[i]=A[i+1]; A[b]=t; } void shift_circular_right(int a,int b) { int t=A[b]; for(int i=b;i>a;i--) A[i]=A[i-1]; A[a]=t; } int main() { int p,q,x,y,m; char type[9]; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) A[i]=i; for(int i=0;i<m;i++) { scanf("%s %d %d",&type,&x,&y); p=find(x); q=find(y); if(type[0]==‘A‘) { if(q>p) shift_circular_left(p,q-1); else shift_circular_right(q,p); } else { if(q>p) shift_circular_left(p,q); else shift_circular_right(q+1,p); } } for(int i=1;i<=n;i++) if(i==1) printf("%d",A[i]); else printf("%d",A[i]); printf("\n"); return 0; }
代码2：
#include<stdio.h> const int MAXN=1000; int n,left[MAXN],right[MAXN]; void link(int X,int Y) { right[X]=Y; left[Y]=X; } int main() { int i,m,X,Y,first=1; char type[9]; scanf("%d %d",&n,&m); right[0]=1; for(i=1;i<=n;i++) { left[i]=i-1; right[i]=i+1; } for(i=0;i<m;i++) { scanf("%s %d %d",&type,&X,&Y); link(left[X],right[X]); if(type[0]==‘A‘) { link(left[Y],X); link(X,Y); } else { link(X,right[Y]); link(Y,X); } } for(int X=right[0];X!=n+1;X=right[X]) if(first) { printf("%d",X); first=0; } else printf("%d",X); printf("\n"); return 0; }