分数: 1000 点
问题陈述
给你一个排列 P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N).
找到一组整数对的序列 ((l_1,r_1),(l_2,r_2),\cdots,(l_k,r_k)) 满足以下所有条件。
- 长度 k 该序列满足 0 \leq k \leq N-1.
- 1 \leq l_i \leq r_i \leq N (1 \leq i \leq k).
- 对于每个 1 \leq i \leq k-1,它认为 r_{i+1} \leq l_i or r_i \leq l_{i+1}.
- 执行以下操作 k 可以排序 P 按升序排列。
- 的 i第 - 次操作:交换的值 P_{l_i} 和 P_{r_i}。 如果 l_i=r_i,什么也不做。
可以证明,在本问题的约束下,这样的序列总是存在。
流程 T 每个输入文件的测试用例。
约束
- 1 \leq T \leq 250000
- 1 \leq N \leq 250000
- P=(P_1,P_2,\cdots,P_N) 是一个排列 (1,2,\cdots,N).
- 总和 N 对于每个输入文件,最多为 250000.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个测试用例 case_i 的格式如下:
N P_1 P_2 \cdots P_N
输出
对于每个测试用例,按以下格式打印解决方案:
k l_1 r_1 l_2 r_2 \vdots l_k r_k
如果存在多个解决方案,则将接受其中任何一个。
示例输入 1
3 3 2 3 1 4 4 3 2 1 1 1
示例输出 1
2 2 3 1 2 3 1 4 1 1 2 3 0
让我们解释一下第一个测试用例。
示例输出满足所有条件。 例如,第四个条件可以按如下方式验证: P=(2,3,1)\to(交换 P_2,P_3)\to(2,1,3)\to(交换 P_1,P_2)\to(1,2,3).
另一方面,以下输出是不正确的:
2 1 2 1 3
这是因为第三个条件没有被满足。