[UVa] 12657 - Boxes in a Line

參考書上的經典鏈結串列題目
有點複雜，花點腦筋想即可
STL會TLE，所以書上用陣列操作

2015/1/16 做了些改良，在書中 swap(x,y) 可拿掉，在後面直接作判斷

if (right[y]==x) {
   link(ly,x); link(x,y); link(y,rx);
}

可達到相同效果
用陣列操作鍊結串列，本就有許多不方便的地方

//STL會TLE，所以改用陣列模擬
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
using namespace std;

const int maxn = 100010;
int left[maxn], right[maxn]; //儲存左邊和右邊盒子序號的陣列
void link(int l, int r){ //連接 l and r ，l在左,r在右
    left[r] = l; right[l] = r;
}
int main(){
// freopen("input.txt","r",stdin);
    int n,m,c,x,y;
    int cas=0;
    while(scanf("%d %d", &n, &m)!=EOF){
      cas++;
        int inv=0;
        for(int i=1;i<=n;i++){
            left[i]=i-1;
            right[i]=(i+1)%(n+1); //尾數的右邊為1
        }
        right[0] = 1;
        left[0] = n;

        while(m--){ 
            scanf("%d",&c);
            if(c==4)inv = !inv;
            else if(c!=3 && inv)c = 3-c; //反向狀態，換的位子要變
            if(c==1){
              scanf("%d %d",&x,&y);
              if(x==left[y])continue;
                link(left[x],right[x]); link(left[y],x); link(x,y);
            }
            else if(c==2){
              scanf("%d %d",&x,&y);
                if(x==right[y])continue;
                int lx = left[x], rx = right[x], ly=left[y], ry=right[y];
              link(lx,rx); link(y,x); link(x,ry);
            }
            else if(c==3){
              scanf("%d %d",&x,&y);
                int lx = left[x], rx = right[x], ly=left[y], ry=right[y];
                if(right[y]==x){ //相鄰情況
                  link(ly,x); link(x,y); link(y,rx);
                }else if(right[x]==y){ //相鄰情況
                  link(lx,y); link(y,x); link(x,ry);
                }else{
                  link(lx,y); link(y,rx); link(ly,x); link(x,ry);
                }
            }
            /*
            int a=0;
            for(int i=1;i<=n;i++){
              a = right[a];
                printf("%d ",a);
            }
            printf("\n");
            */
        }
        int box=0;
        long long sum=0;
        for(int i=1;i<=n;i++){
          box = right[box];
          if(i%2 == 1) sum += box;
        }
        if(inv && n%2==0) sum = (long long)n*(n+1)/2 - sum;
        printf("Case %d: %lld\n",cas,sum);
       
    }
    return 0;
}