← 返回题目列表

AtCoder · wtf22_day1_b

B. 非重叠掉期

中文机器翻译题面 查看原题

分数: 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

这是因为第三个条件没有被满足。