项链

项链⁡\operatorname{项链}项链

题目链接：nowcoder 213760⁡\operatorname{nowcoder\ 213760}nowcoder 213760

到牛客看：

——>点我跳转<——

题目

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

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

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

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

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

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

输入

第一行两个数： NNN 和 MMM

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

输出

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

样例输入

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

样例输出

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

样例解释

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

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

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

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

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

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

数据范围

1≤N≤10000，1≤M≤1000001\leq N\leq 10000，1\le M\le 1000001≤N≤10000，1≤M≤100000

保证操作 444 不超过 505050 次

思路

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

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

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

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

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

代码

#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;
}