P6910: 奶牛晨练
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
Farmer John
的 N
头奶牛（1≤N≤10^5
）站成一排。对于每一个 1≤i≤N
，从左往右数第 i
头奶牛的编号为 i。
Farmer John
想到了一个新的奶牛晨练方案。他给奶牛们 M 对整数 (L1,R1)…(LM,RM)，其中1≤M≤100
。他让她们重复以下包含 M
个步骤的过程 K（1≤K≤10
^9
）次：
1.对于从 1
到 M 的每一个 i：
2.当前从左往右数在位置 Li…Ri
的奶牛序列反转她们的顺序。
当奶牛们重复这一过程 K
次后，请对每一个 1≤i≤N 输出从左往右数第 i 头奶牛的编号。
【
输入格式】
（文件名：swap.in
）：
输入的第一行包含 N, M
和 K。对于每一个 1≤i≤M
，第 i+1
行包含 Li 和 Ri，均为范围在 1…N
内的整数，其中 Li<Ri。
【
输出格式】
（文件名：swap.out
）：
在第 i
行输出指令序列执行了 K
次后奶牛序列中从左往右数第 i 个元素的编号。
【
输入样例】
：
7 2 2
2 5
3 7
【
输出样例】
：
1
2
4
3
5
7
6
【样例说明】
初始时，奶牛们的顺序从左往右为 [1,2,3,4,5,6,7]
。在这一过程的第一步过后，顺序变为 [1,5,4,3,2,6,7]
。在这一过程的第二步过后，顺序变为 [1,5,7,6,2,3,4]
。再重复这两个步骤各一次可以得到样例的输出。
【
测试点性质】
：
测试点 2
满足 N=K=100。
测试点 3-5
满足 K≤10^3
。
测试点 6-10
没有额外限制。