你有一行盒子，从左到右依次编号为1, 2, 3,…, n。你可以执行四种指令： 1 X Y表示把盒子X移动到盒子Y左边（如果X已经在Y的左边则忽略此指令）。 2 X Y表示把盒子X移动到盒子Y右边（如果X已经在Y的右边则忽略此指令）。 3 X Y表示交换盒子X和Y的位置。 4 表示反转整条链。 指令保证合法，即X不等于Y。例如，当n=6时在初始状态下执行1 1 4后，盒子序列为2 3 1 4 5 6。接下来执行2 3 5，盒子序列变成2 1 4 5 3 6。再执行3 1 6，得到2 6 4 5 3 1。最终执行4，得到1 3 5 4 6 2。
Input输入包含不超过10组数据，每组数据第一行为盒子个数n和指令条数m（1<=n,m<=100,000），以下m行每行包含一条指令。
Output每组数据输出一行，即所有奇数位置的盒子编号之和。位置从左到右编号为1~n。
Sample Input 6 41 1 42 3 53 1 646 31 1 42 3 53 1 6100000 14 Sample Output Case 1: 12Case 2: 9Case 3: 2500050000
思路：对每个元素维护两个信息，一个是前驱，一个是后继。。。。
那么只要模拟一下就好，不过这里有个超时的点，就是如果两个节点相邻，3操作会搞错，这个要特判一下。。。。
对于1、2、3就是简单的链表操作了，不过注意3操作有一个坑，就是x和y可能是相邻的两个节点哦，特别注意了，这里有点坑的。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<string> #include<map> #include<set> #include<queue> #include<vector> using namespace std; const int N = 1e5 + 100; const int inf = 1e5 + 10; int pre[N],net[N],a[N]; void link(int p1,int p2) { net[p1]=p2; pre[p2]=p1; } void print(int n) { for(int i=1;i<=n;i++) printf("%d ",a[i]); printf("\n"); } int main() { int n,m,i,j,op,p1,p2,f; int left,right; int cc=0; while(scanf("%d%d",&n,&m)!=EOF) { f=0; for(i=1;i<=n;i++) { pre[i]=i-1; net[i]=i+1; } net[n]=inf; while(m--) { scanf("%d",&op); if(op==4) f=f^1; else { scanf("%d%d",&p1,&p2); if(f) op=3-op; if(op==1) { link(pre[p1],net[p1]); left=pre[p2]; link(left,p1); link(p1,p2); } else if(op==2){ link(pre[p1],net[p1]); right=net[p2]; link(p2,p1); link(p1,right); } else { if(net[p1]==p2 ) { right=net[p2]; link(pre[p1],p2); link(p2,p1); link(p1,right); continue; } if(net[p2]==p1) { swap(p1,p2); right=net[p2]; link(pre[p1],p2); link(p2,p1); link(p1,right); continue; } left=pre[p2]; right=net[p2]; link(pre[p1],p2); link(p2,net[p1]); link(left,p1); link(p1,right); } } } int head = 1,k=0; while(pre[head]!=0 && head!=0) head=pre[head]; while(net[head]!=inf && head!=inf) { a[++k] = head; head = net[head]; } a[++k]=head; if(f) reverse(a+1,a+1+k); long long ans = 0; // print(k); for(i=1;i<=k;i++) if(i&1) ans+=a[i]; printf("Case %d: ",++cc); printf("%lld\n",ans); } return 0; }
