一 问题描述

一行有 n 个盒子，从左到右编号为 1~n。模拟以下 4 种命令。

• 1 X Y：将盒子 X 移动到 Y 的左侧（如果 X 已经在 Y 的左侧，则忽略此项）。
• 2 X Y：将盒子 X 移动到 Y 的右侧（如果 X 已经在 Y 的右侧，则忽略此项）。
• 3 X Y：交换盒子 X 和 Y 的位置。
• 4：翻转整行盒子序列。
  以上命令保证有效，即 X 不等于 Y。

举例说明：有 6 个盒子，执行 1 1 4，即将 1 移到 4 的左侧，变成 2 3 1 4 5 6。然后执行 2 3 5，即 3 移到 5 的右侧，变成 2 1 4 5 3 6。接着执行 3 1 6，即交换 1 和 6 的位置，变成 2 6 4 5 3 1。最后执行 4，即翻转整行序列，变成 1 3 5 4 6 2。
输入：最多有 10 个测试用例。每个测试用例的第 1 行都包含两个整数 n 和 m，n 表示有多少个盒子，m 表示执行多少次操作。

输出：对于每个测试用例，都单行输出奇数索引位置的数字总和。
输入样例

6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
10000 1
4

输出样例

Case 1:12
Case 2:9
Case 3:250005000

二 思路

本问题涉及大量移动元素，因此使用链表比较合适，但是将盒子 X 移到动盒子 Y 的左侧，还需要查找盒子 X 和 盒子 Y 在链表中的位置，查找是链表不擅长的，每次查找时间复杂度都为 O(n),而链表的长度最多为 100 000，多次查找会超时，所以不能使用 list 链表实现。这里可以使用既具有链表特性又具有快速查找能力的静态链表实现，因为问题中既有向前操作，也有向后操作，因此选择静态双向链表。另外，有大量元素的链表，其翻转操作的时间复杂度很高，会超时，此时只需做标记即可，不需要真的翻转。

三 算法设计

1 初始化双向静态链表（前驱数组为 l[],后继数组为 r[]）,翻转标记 flag = false。

2 读入操作指令 a。
3 如果 a=4，则标记翻转，flag = !flag,否则读入 x、y。

4 如果 a!=3&&flag,则 a=3-a。因为如果翻转标记为真，则左右是倒置的，1、2 指令正好相反，即 1 号指令（将 X 移动到 y 左侧）相对于 2 号指令（将 x 移到 y 右侧）。因此如果 a =1，则转换为2；如果a=2，则转换为1。

5 对于1、2指令，如果本来位置就是对的，则什么都不做。
6 如果 a =1，则删除 x，将 x 插入 y 左侧。

7 如果 a =2，则删除 x，将 x 插入 y 右侧。
8 如果 a = 3，则考虑相邻和不相邻两种情况进行处理。

四 算法中的基本操作

1 链接

将 L 和 R 链接起来，则 L 的后继为 R，R 的前驱为 L。

2 删除

删除 x时，只需将 x 跳过去，即将 x 的前驱和后继链接起来即可。

3 插入（将 x 插入 y 左侧）

将 x 插入 y 左侧，先删除 x，然后将 x 插入 y 左侧，删除操作需要1次链接，插入左侧操作需要两次链接。

4 插入（将 x 插入 y 右侧）

将 x 插入 y 右侧，先删除 x，然后将 x 插入 y 右侧，删除操作需要1次链接，插入右侧操作需要两次链接。

5 交换（相邻）

相邻交换统一为3次链接。Lx 和 y 链接，y 和 x 链接，x 和 Ry 链接。

6 交换（不相邻）

不相邻交换统一为4次链接。

7 翻转

如果标记了翻转，且长度 n 为奇数，则正向奇位之和与反向奇数位之和是一样的。

如果标记翻转，且长度 n 为偶数，则反向奇数位之和等于所有元素之和减去正向奇数位之和。

因此只需要统计正向奇数位之和，再判断翻转标记和长度是否为偶数即可。

五 实现

package LinkedListDemo;
import java.math.BigInteger;
import java.util.Scanner;
public class BoxProblem {
    static Integer l[];
    static Integer r[];
    static void init(int n) {
        l = new Integer[n + 1];
        r = new Integer[n + 1];
        for (int i = 1; i <= n; i++) {
            l[i] = i - 1;
            r[i] = (i + 1) % (n + 1);
        }
        r[0] = 1;
        l[0] = n;
    }
    static void link(int L, int R) {
        r[L] = R;
        l[R] = L;
    }
    public static void main(String[] args) {
        // 表示有几个数
        int n;
        // 表示有几次操作
        int m;
        // 操作符号
        int a;
        // 第1个操作数
        int x;
        // 第2个操作数
        int y;
        int k = 0;
        Scanner scanner = new Scanner(System.in);
        boolean flag;
        while (true) {
            n = scanner.nextInt();
            m = scanner.nextInt();
            init(n);
            flag = false;
            for (int i = 0; i < m; i++) {
                a = scanner.nextInt();
                if (a == 4) {
                    flag = !false;
                } else {
                    x = scanner.nextInt();
                    y = scanner.nextInt();
                    if (a == 3 && r[y] == x) {
                        int temp = x;
                        x = y;
                        y = temp;
                    }
                    if (a == 1 && x == l[y]) {
                        continue;
                    }
                    if (a == 2 && x == r[y]) {
                        continue;
                    }
                    int Lx = l[x];
                    int Rx = r[x];
                    int Ly = l[y];
                    int Ry = r[y];
                    if (a == 1) {
                        link(Lx, Rx);
                        link(Ly, x);
                        link(x, y);
                    } else if (a == 2) {
                        link(Lx, Rx);
                        link(y, x);
                        link(x, Ry);
                    } else if (a == 3) {
                        if (r[x] == y) {
                            link(Lx, y);
                            link(y, x);
                            link(Lx, Ry);
                        } else {
                            link(Lx, y);
                            link(y, Rx);
                            link(Ly, x);
                            link(x, Ry);
                        }
                    }
                }
            }
            int t = 0;
            BigInteger sum = BigInteger.valueOf(0);
            for (int i = 1; i < n; i++) {
                t = r[t];
                if (i % 2 == 1) {
                    sum = sum.add(BigInteger.valueOf(t));
                }
            }
            if (flag && n % 2 == 0) {
                sum = BigInteger.valueOf(n).multiply(BigInteger.valueOf(n+1)).divide(BigInteger.valueOf(2)).subtract(sum);
                //sum = BigInteger.valueOf(n * (n + 1) / 2).subtract(sum);
            }
            System.out.println("Case " + (++k) + ":" + sum);
        }
    }
}

六 测试

绿色为输入，白色为输出