$\operatorname{项链}$

题目链接：https://ac.nowcoder.com/acm/problem/213760

到主站看：https://blog.csdn.net/weixin_43346722/article/details/110257456

题目

scimoon 意外得到了一个项链，这个项链非常的神奇：它有 $N$ 个珠子，一开始每个珠子有一个编号，从左到右编号分别是 $1$ 至 $N$ ，scimoon 进行了 $M$ 次操作，每次操作有下面这么几种：

1 x y：表示将编号为 $x$ 的珠子移到编号为 $y$ 的珠子的后面

2 x y：表示将编号为 $x$ 的珠子移到编号为 $y$ 的珠子的前面

3：表示翻转这个项链，注意翻转后 $1,2$ 操作中的前后关系会改变

4：从编号 $1$ 的珠子开始从左到右输出每个珠子的编号

如果您没有完全理解题意，您可以通过阅读样例解释帮助理解

输入

第一行两个数： $N$ 和 $M$

第 $2\sim M+1$ 行：输入每一次操作

输出

对于每次操作 $4$ ，输出这个项链每位置上的珠子的编号。

样例输入

样例输出

1 3 4 2 5
1 5 3 4 2
1 2 4 3 5

样例解释

第一次操作后， $2$ 号珠子被放到了 $4$ 号珠子的后面，项链为 $[1,3,4,2,5]$

第二次操作输出当前的项链 $[1,3,4,2,5]$

第三次操作后， $5$ 号珠子被放到了 $3$ 号珠子的前面，项链为 $[1,5,3,4,2]$

第四次操作输出当前的项链 $[1,5,3,4,2]$

第五次操作翻转当前项链 $[2,4,3,5,1]$

第六次操作中，由于我们需要从 $1$ 开始输出项链，因此输出 $[1,2,4,3,5]$

数据范围

$1\leq N\leq 10000，1\le M\le 100000$

保证操作 $4$ 不超过 $50$ 次

思路

这道题其实就是一个链的模拟。

因为要翻转，那我们就模拟双向的。

然后就把翻转了奇数次和翻转了偶数次的情况下的模拟分开来写。

然后讲一下每一个操作要怎么模拟：（这里默认翻转偶数次，就是正常的从左到右）

操作一，把一个珠子 $a$ 移到珠子 $b$ 的后面。那就是 $a$ 左右要连起来， $b$ 的后面就是 $a$ ， $a$ 的后面就是 $b$ 原来的后面。（写代码的时候按上面的顺序反过来写，才不会要用的值被之前覆盖）
操作二，把一个珠子 $a$ 移到珠子 $b$ 的前面。那其实差不多，也是 $a$ 左右连起来，那这一次就是 $a$ 的前面是 $b$ 原来的后面， $a$ 的后面是 $b$ 。（写代码的时候也要反过来，原因一样）
操作三，翻转。那其实简单，就弄一个 $turn$ 记录它当前是正的反的。然后又一次操作三就 $turn\ \oplus = 1$
操作四，输出。那更容易，如果现在是正的就直接从左到右输出，否则就从右到左输出。
代码

#include<cstdio>

using namespace std;

int n, m, bef[10001], nxt[10001], turn, op, x, y;

int main() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        bef[i] = i - 1;
        nxt[i] = i + 1;
    }
    bef[1] = n;
    nxt[n] = 1;

    for (int i = 1; i <= m; i++) {
        scanf("%d", &op);

        if (op == 1) {
            scanf("%d %d", &x, &y);

            if (!turn) {
                nxt[bef[x]] = nxt[x];
                bef[nxt[x]] = bef[x];
                bef[nxt[y]] = x;
                nxt[x] = nxt[y];
                bef[x] = y;
                nxt[y] = x;
            }
            else {
                nxt[bef[x]] = nxt[x];
                bef[nxt[x]] = bef[x];
                nxt[bef[y]] = x;
                bef[x] = bef[y];
                nxt[x] = y;
                bef[y] = x;
            }

            continue;
        }
        if (op == 2) {
            scanf("%d %d", &x, &y);

            if (!turn) {
                nxt[bef[x]] = nxt[x];
                bef[nxt[x]] = bef[x];
                nxt[bef[y]] = x;
                bef[x] = bef[y];
                nxt[x] = y;
                bef[y] = x;
            }
            else {
                nxt[bef[x]] = nxt[x];
                bef[nxt[x]] = bef[x];
                bef[nxt[y]] = x;
                nxt[x] = nxt[y];
                bef[x] = y;
                nxt[y] = x;
            }

            continue;
        }
        if (op == 3) {
            turn ^= 1;

            continue;
        }
        if (op == 4) {
            if (!turn) {
                printf("1 ");
                for (int j = nxt[1]; j != 1; j = nxt[j])
                    printf("%d ", j);
                printf("\n");
            }
            else {
                printf("1 ");
                for (int j = bef[1]; j != 1; j = bef[j])
                    printf("%d ", j);
                printf("\n");
            }

            continue;
        }
    }

    return 0;
}

项链