你有一行盒子，从左到右依次编号为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。

输入包含不超过10组数据，每组数据第一行为盒子个数n和指令条数m（1<=n,m<=100,000），以下m行每行包含一条指令。

每组数据输出一行，即所有奇数位置的盒子编号之和。位置从左到右编号为1~n。

  1 #include"stdio.h"  2 #include"string.h"  3 const int ms=100004;  4 int left[100004];  5 int right[100004];  6 int *tmp1,*tmp2;  7 inline void link(int a,int b)  8 {  9     right[a]=b; 10     left[b]=a; 11 } 12 int main() 13 { 14     int n,m,i,j,k,flag,x,y,p=1,cnt,next; 15     while(scanf("%d%d",&n,&m)!=EOF) 16     { 17         for(i=1;i<=n;i++) 18         { 19             left[i]=i-1; 20             right[i]=i+1; 21         } 22         right[n]=0;//构成环，方便寻找开始节点和结束节点  23         cnt=0; 24         while(m--) 25         { 26             scanf("%d",&flag); 27             if(flag!=4) 28                 scanf("%d%d",&x,&y); 29             else 30                 cnt++; 31             if((cnt&1)&&flag<3) 32                 flag=3-flag; 33             if(flag==1&&(right[x]!=y)) 34             { 35                 if(right[y]==x) 36                 { 37                     int t1=left[x],t2=right[x],t3=left[y],t4=right[y]; 38                     link(t3,x); 39                     link(x,y); 40                     link(y,t2); 41                 } 42                 else 43                 { 44                     link(left[x],right[x]); 45                     link(left[y],x); 46                     link(x,y); 47                 } 48             } 49             else if(flag==2&&right[y]!=x) 50             { 51                 if(right[x]==y) 52                 { 53                     int t1=left[x],t2=right[x],t3=left[y],t4=right[y]; 54                     link(t1,y); 55                     link(y,x); 56                     link(x,t4);     57                 } 58                 else 59                 { 60                     link(left[x],right[x]); 61                     link(x,right[y]); 62                     link(y,x); 63                 } 64             } 65             else if(flag==3) 66             { 67                 if(right[x]==y) 68                 { 69                     int t1=left[x],t2=right[x],t3=left[y],t4=right[y]; 70                     link(t1,y); 71                     link(y,x); 72                     link(x,t4); 73                 } 74                 else if(right[y]==x) 75                 { 76                     int t1=left[x],t2=right[x],t3=left[y],t4=right[y]; 77                     link(t3,x); 78                     link(x,y); 79                     link(y,t2); 80                 } 81                 else{ 82                     int t1=left[x],t2=right[x],t3=left[y],t4=right[y]; 83                     link(t1,y); 84                     link(y,t2); 85                     link(t3,x); 86                     link(x,t4); 87                 } 88             } 89         } 90         long long ans=0; 91         if(cnt&1) 92         { 93             tmp2=right; 94             tmp1=left; 95         } 96         else 97         { 98             tmp2=left; 99             tmp1=right;100         }101         for(i=1;i<=n;i++)102         {103             if(tmp2[i]==0)104             {105                 for(k=1;i;i=tmp1[i],k++)106                     if(k&1)107                         ans+=i;108                 printf("Case %d: %lld\n",p++,ans);109                 break;110             }111         }112     }113     return 0;114 }