AT_arc180_b [ARC180B] Improve Inversions

题目描述

给定一个 $(1,2,\cdots,N)$ 的排列 $P=(P_1,P_2,\cdots,P_N)$，以及一个整数 $K$。

你可以进行如下操作 $0$ 次或多次：

• 选择整数 $l,r$（$1\leq l<r\leq N$），但需满足以下所有条件：
  • $K\leq r-l$。
  • 当前 $P_l>P_r$。
  • 之前从未选择过同一组 $(l,r)$。
• 然后交换 $P_l$ 和 $P_r$ 的值。

你希望最大化操作次数。请给出一种实现方法。

输入格式

输入通过标准输入按以下格式给出：

$N$ $K$ $P_1$ $P_2$ $\cdots$ $P_N$

输出格式

请按以下格式输出答案：

$m$ $l_1$ $r_1$ $l_2$ $r_2$ $\vdots$ $l_m$ $r_m$

其中 $m$ 是最大操作次数，$l_i,r_i$ 是第 $i$ 次操作选择的 $l,r$。如果有多种方案，输出任意一种即可。

样例 1

输入

3 1
3 2 1

输出

3
2 3
1 3
1 2

样例 2

输入

5 4
1 4 3 2 5

输出

0

样例 3

输入

4 2
4 1 2 3

输出

2
1 4
1 3

样例 4

输入

10 5
8 7 6 10 9 3 1 5 2 4

输出

15
3 8
2 8
3 10
3 9
1 8
2 10
2 9
2 7
1 10
5 10
1 9
4 10
4 9
1 7
1 6

说明/提示

限制条件

• $2\leq N\leq 500$
• $1\leq K\leq N-1$
• $(P_1,P_2,\cdots,P_N)$ 是 $(1,2,\cdots,N)$ 的一个排列
• 输入的所有值均为整数

样例解释 1

在本例中，最大操作次数为 $3$。输出样例的操作过程如下：

• 第 $1$ 次操作：选择 $(l,r)=(2,3)$。$1\leq 3-2$，$P_2>P_3$，且未选过 $(2,3)$，满足条件。交换 $P_2,P_3$，$P=(3,1,2)$。
• 第 $2$ 次操作：选择 $(l,r)=(1,3)$。$1\leq 3-1$，$P_1>P_3$，且未选过 $(1,3)$，满足条件。交换 $P_1,P_3$，$P=(2,1,3)$。
• 第 $3$ 次操作：选择 $(l,r)=(1,2)$。$1\leq 2-1$，$P_1>P_2$，且未选过 $(1,2)$，满足条件。交换 $P_1,P_2$，$P=(1,2,3)$。

由 ChatGPT 4.1 翻译