双向链表
注意：如果算法是最后处理翻转情况时，注意指令4翻转后1,2两个指令也要翻转处理；
指令3 中交换盒子要注意两个盒子相邻的情况
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 int ri[100010],le[100010]; 6 7 void link (int l,int r){ 8 ri[l]=r;le[r]=l; 9 } 10 11 void moveleft (int l,int r){ 12 link (le[l],ri[l]); 13 link (le[r],l); 14 link (l,r); 15 } 16 17 void moveright (int l,int r){ 18 link (le[l],ri[l]); 19 link (l,ri[r]); 20 link (r,l); 21 } 22 23 void exchange (int l,int r){ 24 int ll,rl,lr,rr; 25 ll=le[l];rl=ri[l];lr=le[r];rr=ri[r]; 26 if (ll==r){ 27 link (lr,l);link (l,r);link (r,rl); 28 } 29 else if (l==lr){ 30 link (ll,r);link (r,l);link (l,rr); 31 } 32 else { 33 link (ll,r);link (r,rl); 34 link (lr,l);link (l,rr); 35 } 36 } 37 38 int main (){ 39 int n,m,kase=0,inv; 40 while (cin>>n>>m){ 41 inv=0; 42 memset (ri,0,sizeof ri); 43 memset (le,0,sizeof le); 44 for (int i=0;i<=n;i++) 45 link (i,i+1); 46 for (int i=0;i<m;i++){ 47 int c; 48 cin>>c; 49 if (c==4) 50 inv++; 51 else { 52 int x,y; 53 cin>>x>>y; 54 if (x==y) 55 continue ; 56 if (inv%2) //经过指令4后指令1,2也要翻转处理； 57 c=3-c; 58 if (c==1){ 59 moveleft (x,y); 60 } 61 else if (c==2){ 62 moveright (x,y); 63 } 64 else { 65 exchange (x,y); 66 } 67 } 68 //int temp=0; 69 //for (int i=ri[0];i<=n&&temp<n;i=ri[i]){ 70 // cout<<i<<" "; 71 // temp++; 72 //} 73 } 74 long long ans=0; 75 int f; 76 if (n%2) 77 f=0; 78 else f=inv%2; 79 int temp=0; 80 for (int i=ri[0];i<=n&&temp<n;i=ri[i]){// cout<<ri[i]<<" "; 81 if (temp%2==f){ 82 ans+=i; 83 } 84 temp++; 85 } 86 cout<<"Case "<<++kase<<": "; 87 cout<<ans<<endl; 88 } 89 return 0; 90 }