#2848. 「ROI 2018 Day 2」快速排序

内存限制:256 MiB 时间限制:750 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

译自 ROI 2018 Day2 T2. Быстрая сортировка (Quick sort)

给一个包含 n 个元素的排列 [a_1, a_2, \ldots, a_n]
定义操作 S(l, r), 表示:将数列的片段 [a_l, a_{l+1}, \ldots, a_r] 重排成 [a_{l+1}, a_{l+3}, \ldots, a_l, a_{l+2}, \ldots]
举个例子: [2, 4, 1, 5, 3, 6, 7, 8]\xrightarrow{\,S(2,6)\,} [2, 1, 3, 4, 5, 6, 7, 8], 其中子串 [4, 1, 5, 3, 6] 被重排成了 [1, 3, 4, 5, 6]
给定一个排列,试求经过多少次操作能使排列变成递增顺序,并输出任意一组方案,要求方案的操作次数最少,但要求操作次数 \leqslant 15000

输入格式

第一行一个整数 n\ \left( 1 \leqslant n \leqslant 3000 \right) ,表示排列 a 的大小。
接下来有 n 个不同的数 a_1,\ a_2,\ \ldots,\ a_n ,表示排列 a

输出格式

第一行一个整数 k ,表示你的操作次数。 需要满足 0 \leqslant k \leqslant 15000
接下来 k 行,你需要按照操作顺序描述你的操作。对于每一步操作,输出两个数 L , R ,表示你对片段 a_L,\ a_{L+1},\ \ldots,\ a_R 执行了一次操作。 需满足 1 \leqslant L \leqslant R \leqslant n
注意,你需要最小化。你只需保证 0 \leqslant k \leqslant 15000 即可。保证存在这样的 k

样例

样例输入 1

5
3 1 4 2 5

样例输出 1

1
1 5

样例输入 2

8
2 4 1 5 3 6 7 8

样例输出 2

2
2 6
1 2

样例输入 3

2
2 1

样例输出 3

3
1 1
2 2
1 2

样例说明 3

显然 S(1,1) S(2,2) 并没有什么卵用
举这个例子是告诉你,不要求方案的操作次数最少。

数据范围与提示

k_0 表示最小操作次数。
对于所有数据, 1\leqslant n\leqslant 3000, 0\leqslant k_0\leqslant 15000, 1\leqslant a_i\leqslant n, a_i 互不相同。

子任务编号 分值 1\leqslant n\leqslant 其它
1 20 100 k_0=1
2 30 100
3  30  1000  
4 20 3000