LRJ入门经典（基础篇）——5.移动的盒子

5.移动的盒子

问题描述：
你有一行盒子，从左到右依次编号为1,2,3,…,n。可以执行以下4种指令：
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 2 3 4 5 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，以下m行每行包含一条指令。
【输出格式】
每组数据输出一行，即所有奇数位置的盒子编号之和。位置从左到右编号为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
【数据范围】
N,M<=100000
分析：
链表的应用

#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;
        //执行命令
        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;
}

测试数据：

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