Swapity Swapity Swap

题目描述

农夫约翰的 $N$ 头奶牛（$1\le N\le 10^5$）站成一排。从左到右第 $i$ 头奶牛的标签为 $i$，对每个 $1\le i\le N$ 都成立。 农夫约翰为奶牛们想出了一套新的晨练流程。他给出了奶牛们 $M$ 对整数 $(L_1,R_1) \ldots (L_M, R_M)$，其中 $1 \leq M \leq 100$。随后他让奶牛们将下面这个包含 $M$ 步的过程恰好重复 $K$ 次（$1\le K\le 10^9$）： 对每个 $i$ 从 $1$ 到 $M$： 当前位于从左数位置 $L_i \ldots R_i$ 的奶牛序列反转其顺序。 在奶牛们恰好重复该过程 $K$ 次之后，请输出从左到右第 $i$ 头奶牛的标签（对每个 $1\le i\le N$）。

输入格式

第一行包含 $N$、$M$ 和 $K$。 对每个 $1\le i\le M$，第 $i+1$ 行包含 $L_i$ 和 $R_i$，二者均为范围 $1 \ldots N$ 内的整数，且满足 $L_i < R_i$。

输出格式

输出共 $N$ 行。 在第 $i$ 行，输出执行该指令串 $K$ 次后数组的第 $i$ 个元素。

7 2 2
2 5
3 7

1
2
4
3
5
7
6

提示

评分： 测试点 2 满足 $N=K=100$。 测试点 3-5 满足 $K\le 10^3$。 测试点 6-10 无额外限制。

起初，奶牛的顺序（从左到右）为 $[1,2,3,4,5,6,7]$。在该过程的第一步之后，顺序为 $[1,5,4,3,2,6,7]$。在该过程的第二步之后，顺序为 $[1,5,7,6,2,3,4]$。将这两步再重复一次即可得到样例输出。

题目致谢：Brian Dean

标签: USACO|2020|Silver

来源

USACO|2020|Silver