Description
你有一行盒子，从左到右依次编号为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
Hint
Source
湖南省第九届大学生计算机程序设计竞赛
思路：
这个题拿到脑子里应该会想到用链表，因为方便插入删除，不用像数组那么复杂。
可是难点在于把整个串反转的时候需要会不会TE.
处理方法很巧妙：
我们用数组模拟链表（你也可以链表一个*next指向下一个，一个*previous指向上一个），我采用l,r来指向左右单元的数。
其实每次移动不用把数组里的单元格移动，只需要改变单元格的l,r就可以达到同样的效果。
如4个盒子
0 1 2 3 4
-1 1 0 2 1 3 2 4 3 5（l,r）
把1移动到4左边，则变为
0 1 2 3 4
-1 23 4 0 3 2 1 1 5
另外需要注意的是，进行3操作时，我们需要注意。具体见代码注释。、
还有进行四操作时，并不需要把整个串反过来，只要要反着进行1，2操作就行，就像正着来插入在左边，反着来就插入在右边。判断出现次数奇偶就行。
#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
struct node
{int l,r;
}box[100005];
/*int cmp(box a,box b)
{return a.l<b.l;
}*/
int main()
{int n,m,flag,cnt=0;while(scanf("%d %d",&n,&m)!=EOF){//cnt=0;flag=0;for(int i=0;i<=n;i++){box[i].l=i-1;box[i].r=i+1;}/* for(int i=0;i<=n;i++){cout<<box[i].l<<" "<<box[i].r<<endl;}*/int a,b,c;for(int i=0;i<m;i++){scanf("%d",&a);////cout<<"-----------"<<endl;if(a==4) flag^=1;//异或操作，看出现四操作次数为奇数还是偶数else{scanf("%d %d",&b,&c);if(a==3){ //注意3的交换操作int tmp;if(box[b].l==c)//注意不要出现自己的左边或右边为自己的请况{box[box[b].r].l=c; box[box[c].l].r=b;box[b].l = box[c].l; box[c].l=b;box[c].r = box[b].r; box[b].r=c;}else if(box[c].l==b){//与上同理box[box[c].r].l=b; box[box[b].l].r=c;box[c].l = box[b].l; box[b].l=c;box[b].r = box[c].r; box[c].r=b;}else{//一般情况box[box[b].l].r= c ; box[box[b].r].l = c;box[box[c].l].r= b ; box[box[c].r].l = b;tmp = box[b].l ; box[b].l=box[c].l; box[c].l=tmp;tmp = box[b].r ; box[b].r=box[c].r; box[c].r=tmp;}continue ;}if(flag) a=3-a;if(a==1)///b移动到c左边{if(box[b].r==c&&box[c].l==b) continue;box[box[b].l].r=box[b].r;box[box[b].r].l=box[b].l;box[b].l=box[c].l;box[b].r=box[box[c].l].r;box[box[c].l].r=b;box[c].l=b;}else if(a==2)///b移动到c右边{if(box[c].r==b&&box[b].l==c) continue;box[box[b].l].r=box[b].r;box[box[b].r].l=box[b].l;box[b].r=box[c].r;box[b].l=c;box[box[c].r].l=b;box[c].r=b;}}}/* for(int i=0;i<=n;i++){cout<<box[i].l<<" "<<box[i].r<<endl;}*/int kk=1;int ans;long long sum=0;if(flag){ans=box[0].r;while(kk<=n){//cout<<ans<<" "<<kk<<"\\\';if(!(kk&1)){// cout<<ans<<endl;sum+=ans;//cout<<sum<<endl;//cout<<ans<<" ";}ans=box[ans].r;kk++;}}else{ans=box[0].r;while(kk<=n){//cout<<ans<<" ";if(kk&1)sum+=ans;ans=box[ans].r;kk++;}}//cout<<endl;printf("Case %d: %lld\n",++cnt,sum);}return 0;
}