5.移動的盒子

問題描述：
你有一行盒子，從左到右依次編號為1,2,3,…,n。可以執(zhí)行以下4種指令：
1 x y：表示把盒子x移動到盒子y的左邊（若x已經(jīng)在y的左邊則忽略此指令）。
2 x y：表示把盒子x移動到盒子y的右邊（如果x已經(jīng)在y的右邊則忽略此指令）。
3 x y：表示交換盒子x和y的位置。
4：表示反轉(zhuǎn)整條鏈。
指令保證合法，即x不等于y。
例如:
當(dāng)n=6時在初始狀態(tài)盒子序列為為：1 2 3 4 5 6；
執(zhí)行1 1 4后，盒子序列為：2 3 1 4 5 6；
接下來執(zhí)行2 3 5，盒子序列變?yōu)椋? 1 4 5 3 6；
再執(zhí)行3 1 6，盒子序列變?yōu)椋? 6 4 5 3 1；
最終執(zhí)行4，盒子序列變?yōu)椋? 3 5 4 6 2。
【輸入格式】
輸入包含不超過10組數(shù)據(jù)，每組數(shù)據(jù)第一行為盒子數(shù)n和指令m，以下m行每行包含一條指令。
【輸出格式】
每組數(shù)據(jù)輸出一行，即所有奇數(shù)位置的盒子編號之和。位置從左到右編號為1~n。
【輸入樣例】
6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
100000 1
4
【輸出樣例】
12
9
2500050000
【數(shù)據(jù)范圍】
N,M<=100000
分析：
鏈表的應(yīng)用

#include <cstdio>
const int maxn = 100005;
int right[maxn],left[maxn];
/** */
void swap(int x,int y){//交換
    int x_left, x_right, y_left, y_right;
    x_left = left[x];
    x_right = right[x];
    y_left = left[y];
    y_right = right[y];
    
    right[x_left] = y;
    right[y] = x_right;
    right[y_left] = x;
    right[x] = y_right;
    
    left[x_right] = y;
    left[y] = x_left;
    left[y_right] = x;
    left[x] = y_left;
}

void set_left(int x, int y){//放左邊
    int x_left,y_left,x_right,y_right;
    x_left = left[x];
    y_left = left[y];
    x_right = right[x];
    y_right = right[y];
    
    right[x_left] = x_right;
    right[y_left] = x;
    right[x] = y;
    
    left[x_right] = x_left;
    left[y] = x;
    left[x] = y_left;
}

void set_right(int x, int y){//放右邊
    int x_left,y_left,x_right,y_right;
    x_left = left[x];
    y_left = left[y];
    x_right = right[x];
    y_right = right[y];
    
    right[x_left] = x_right;
    right[y] = x;
    right[x] = y_right;
    
    left[x_right] = x_left;
    left[y_right] = x;
    left[x] = y;
}
int main(){
    
    int n, m;
    long long ans=0;
    while(scanf("%d%d",&n,&m) == 2){
        //初始化鏈表
        for(int i = 1; i <= n; i++){
            left[i] = i-1;
            right[i] = (i+1) % (n+1);
            
        }
        right[0] = 1;
        left[0] = n;
        //執(zhí)行命令
        int op, x, y;
        //bool REVERSE = false;
        while(m--){
            scanf("%d",&op);
            if(op == 4){
                int temp[n];
                for(int i = 0;i<=n;i++){
                    temp[i] = right[i];
                    right[i] = left[i];
                    left[i] = temp[i];
                }
            }else{
                scanf("%d%d",&x,&y);
                if(op == 1 && right[x] == y) continue;
                if(op == 2 && right[y] == x) continue;
                if(op == 1 && right[x] != y) set_left(x, y);
                if(op == 2 && right[y] != x) set_right(x,y);
                if(op == 3) swap(x, y);
            }
        }
        
        int count = 0;
        for(int i = 0;count < n;i=right[i]){
            if(count%2 == 0) ans += right[i];
            count++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

測試數(shù)據(jù)：

6 4
1 1 4
2 3 5
3 1 6
4
12