循环玩具游戏

一 问题描述

有个名为 Looploop 的玩具，这个玩具有 N 个元素，以循环方式排列。有一个箭头指向其中一个元素，还有两个预设参数 k1 和 k 2。

上图显示了一个由 6 个元素组成的循环。假设预设参数 k1=3，k2 =4，对这个玩具做 6 种操作，请对这些操作中的每个查询都给出答案。

1 加 x（add x ）

从箭头指向的元素开始，将顺时针方向第 1～k2 个元素加 x 。

2 反转（reverse）

从箭头指向的元素开始，将顺时针方向第 1～k1 个元素反转。

3 插入x （insert x ）

在箭头指向的元素右侧（顺时针方向）插入一个新元素 x 。

4 删除（delete）

删除箭头指向的元素，然后将箭头移到其右侧的元素上。

5 移动 x （move x ）

x 只可以是 1 或 2。若 x=1，则向左（逆时针方向）移动箭头；若 x=2，则向右移动箭头。

6 查询（query）

在一行中输出箭头指向的元素。

二 输入和输出说明

1 输入

输入包含多个测试用例。每个测试用例的第 1 行都包括 N、M 、k1 、k2 （2≤k 1

2 输出

对每个测试用例，都在第 1 行输出用例数（格式如输出样例），然后对用例中的每个查询，都单行输出箭头指向的元素。

三 输入和输出样例

1 输入样例

5 1 2 4

3 4 5 6 7

query

5 13 2 4

1 2 3 4 5

move 2

query

insert 8

reverse

query

add 2

query

move 1

query

move 1

query

delete

query

0 0 0 0

2 输出样例

Case #1:

3

Case #2:

2

8

10

1

5

1

四 分析

本问题包含6种操作：区间修改、区间反转、插入、删除、移动、查询。

1 add x

从箭头指向的元素开始，将顺时针方向第 1～k2 个元素加 x。

2 reverse

从箭头指向的元素开始，将顺时针方向第 1～k1个元素反转。

3 insert x 

在箭头指向的元素右侧插入一个新元素 x 。

4 delete

删除箭头指向的元素，然后将箭头移到右侧的元素上。

5 move x

若 x 等于1，则箭头向左移一位；若x 等于2，则箭头向右移一位。

6 query

输出箭头指向的元素。

五 图解

测试用例 2 的输入数据 5 13 2 4，表示元素的初始数量 N=5，将执行的操作总数 M=13，两个预设参数 k1=2，k2=4。

1 初始状态为1 2 3 4 5。

2 move 2

向右移动。query：查询箭头所指向的元素，输出 2。

3 insert 8

在箭头指向的元素右侧（顺时针方向）插入 8。

4 reverse

从箭头指向的元素开始，将顺时针方向第 1～k1（k 1 =2）个元素反转。query：查询箭头指向的元素，输出 8。

5 add 2

从箭头指向的元素开始，将顺时针方向第 1～k2 （k2 =4）个元素加 2。query：查询箭头指向的元素，输出 10。

6 move 1

将箭头向左移动1位。query：查询箭头指向的元素，输出 1。

7 move 1

将箭头向左移动 1 位。query：查询箭头指向的元素，输出 5。

8 delete

删除箭头指向的元素，然后将箭头移至右侧元素上。query：查询箭头指向的元素，输出1

六 算法设计

本题可采用伸展树解决，在首尾添加两个虚节点。箭头指向的元素永远在第 2 个位置（首尾添加了虚节点），过程如下。

1 add x

从箭头指向的元素开始，将顺时针方向第 1～k2 个元素加 x 。箭头所指向的元素在第 2 个位置，因此执行区间修改 Add(2,k2+1, x )。

2 reverse

从箭头指向的元素开始，将顺时针方向第 1～k1个元素反转。执行区间反转 Reverse(2, k1 +1)。

3 insert x 

在箭头指向的元素右侧插入x 。在第 2 个位置右侧插入x ，执行 Insert(2, x )。

4 delete

删除箭头指向的元素，将箭头移到右侧的元素上。删除第 2 个位置的元素，执行Delete(2)。

5 move x 

若 x=1，则箭头向左移一位，相当于删除元素 An ，把 An 放在第1个位置之后。执行 y=Delete(sum+1); Insert(1, y)，sum 为实际的元素个数。

若 x =2，则箭头向右移一位，相当于把元素 A1 删除，然后把 A1 放在 An 之后。执行y=Delete(2); Insert(sum+1, y )。

七 代码

package com.platform.modules.alg.alglib.hdu4453;
 
public class Hdu4453 {
    private int maxn = 200100;
    private int inf = 0x3f3f3f3f;
    int n, cnt, root; // 结点数，结点存储下标累计，树根
    int pos, sum; // 当前箭头位置，数字数量
    int a[] = new int[maxn];
    String op;
    private node tr[] = new node[maxn];
    public String output = "";
 
    public Hdu4453() {
        for (int i = 0; i < tr.length; i++) {
            tr[i] = new node();
        }
    }
 
    public String cal(String input) {
        int m, k1, k2;
        String[] line = input.split("\n");
        String[] num = line[0].split(" ");
        n = Integer.parseInt(num[0]);
        m = Integer.parseInt(num[1]);
        k1 = Integer.parseInt(num[2]);
        k2 = Integer.parseInt(num[3]);
        int x;
 
        if (n == 0) return output;
        String[] element = line[1].split(" ");
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(element[i - 1]);
        }
        Init();
        pos = 2;
        sum = n;
        int count = 2;
        for (int i = 1; i <= m; i++) {
            String[] command = line[count++].split(" ");
            op = command[0];
            switch (op.charAt(0)) {
                case 'a':
                    x = Integer.parseInt(command[1]);
                    Add(2, k2 + 1, x);
                    break;
                case 'r':
                    Reverse(2, k1 + 1);
                    break;
                case 'i':
                    x = Integer.parseInt(command[1]);
                    Insert(2, x);
                    break;
                case 'd':
                    Delete(2);
                    break;
                case 'm':
                    x = Integer.parseInt(command[1]);
                    if (x == 1) {
                        int y = Delete(sum + 1);
                        Insert(1, y);
                    } else {
                        int y = Delete(2);
                        Insert(sum + 1, y);
                    }
                    break;
                case 'q':
                    Query(2);
                    break;
            }
        }
 
        return output;
    }
 
 
    void Update(int x) {
        tr[x].size = 1;
        if (tr[x].son[0] > 0)
            tr[x].size += tr[tr[x].son[0]].size;
        if (tr[x].son[1] > 0)
            tr[x].size += tr[tr[x].son[1]].size;
    }
 
    void Pushdown(int x) {
        if (tr[x].rev == 1) { // 下传翻转标记
            tr[x].rev ^= 1;
            int temp = tr[x].son[0];
            tr[x].son[0] = tr[x].son[1];
            tr[x].son[1] = temp;
            if (tr[x].son[0] > 0)
                tr[tr[x].son[0]].rev ^= 1;
            if (tr[x].son[1] > 0)
                tr[tr[x].son[1]].rev ^= 1;
        }
        if (tr[x].add > 0) { // 下传加标记
            if (tr[x].son[0] > 0) {
                tr[tr[x].son[0]].add += tr[x].add;
                tr[tr[x].son[0]].val += tr[x].add;
            }
            if (tr[x].son[1] > 0) {
                tr[tr[x].son[1]].add += tr[x].add;
                tr[tr[x].son[1]].val += tr[x].add;
            }
            tr[x].add = 0;//清除标记
        }
    }
 
    // 生成新结点
    int New(int father, int val) {
        tr[++cnt].fa = father;
        tr[cnt].val = val;
        tr[cnt].size = 1;
        tr[cnt].add = tr[cnt].rev = 0;
        tr[cnt].son[0] = tr[cnt].son[1] = 0;
        return cnt;
    }
 
    // 旋转
    void Rotate(int x) {
        Pushdown(x);
        int y = tr[x].fa, z = tr[y].fa;
        int c = (tr[y].son[0] == x) ? 1 : 0;
        tr[y].son[1 - c] = tr[x].son[c];
        tr[tr[x].son[c]].fa = y;
        tr[x].fa = z;
        if (z > 0)
            tr[z].son[tr[z].son[1] == y ? 1 : 0] = x;
        tr[x].son[c] = y;
        tr[y].fa = x;
        Update(y);
        Update(x);
    }
 
    // 将 x 旋转为 goal 的儿子
    void Splay(int x, int goal) {
        while (tr[x].fa != goal) {
            int y = tr[x].fa, z = tr[y].fa;
            if (z != goal) {
                if (((tr[z].son[0] == y ? 1 : 0) ^ (tr[y].son[0] == x ? 1 : 0)) == 0) {
                    Rotate(y);
                } else {
                    Rotate(x);
                }
            }
            Rotate(x);
        }
        // 如果 goal 是 0，则更新根为 x
        if (goal == 0) root = x;
    }
 
    int Findk(int x, int k) {
        while (true) {
            Pushdown(x);
            int sn = tr[x].son[0] > 0 ? tr[tr[x].son[0]].size + 1 : 1;
            if (k == sn)
                return x;
            if (k > sn) {
                k -= sn;
                x = tr[x].son[1];
            } else
                x = tr[x].son[0];
        }
    }
 
    // 插入值val
    void Insert(int pos, int val) {
        int x = Findk(root, pos);
        int y = Findk(root, pos + 1);
        Splay(x, 0);
        Splay(y, x);
        tr[y].son[0] = New(y, val);
        Update(y);
        Update(x);
        sum += 1;
    }
 
    // 删除
    int Delete(int pos) {
        int x = Findk(root, pos - 1);
        int y = Findk(root, pos + 1);
        Splay(x, 0);
        Splay(y, x);
        int tmp = tr[tr[y].son[0]].val;
        tr[y].son[0] = 0;
        Update(y);
        Update(x);
        sum -= 1;
        return tmp;
    }
 
    int Build(int l, int r, int t, int fa) {
        if (l > r)
            return t;
        int mid = l + r >> 1;
        t = New(fa, a[mid]);
        tr[t].son[0] = Build(l, mid - 1, tr[t].son[0], t);
        tr[t].son[1] = Build(mid + 1, r, tr[t].son[1], t);
        Update(t);
        return t;
    }
 
    void Init() {
        cnt = root = 0;
        tr[0].son[0] = tr[0].son[1] = 0;
        root = New(0, -inf);//创建虚结点1
        tr[root].son[1] = New(root, inf);//创建虚结点2
        tr[root].size = 2;
        tr[tr[root].son[1]].son[0] = Build(1, n, tr[tr[root].son[1]].son[0], tr[root].son[1]);
        Update(tr[root].son[1]);
        Update(root);
    }
 
    // [l,r]区间加上 val
    void Add(int l, int r, int val) {
        int x = Findk(root, l - 1), y = Findk(root, r + 1);
        Splay(x, 0);
        Splay(y, x);
        tr[tr[y].son[0]].val += val;
        tr[tr[y].son[0]].add += val;
        Update(y);
        Update(x);
    }
 
    // [l,r] 区间翻转
    void Reverse(int l, int r) {
        int x = Findk(root, l - 1), y = Findk(root, r + 1);
        Splay(x, 0);
        Splay(y, x);
        tr[tr[y].son[0]].rev ^= 1; // 加翻转标记
    }
 
    // 查询
    void Query(int pos) {
        int x = Findk(root, pos);
        output += tr[x].val + "\n";
    }
}
 
class node {
    int son[] = new int[2]; // 左右孩子0,1
    int val, fa;//值，父亲
    int size, add, rev;//大小，加标记，翻转标记
}

八 测试