CF1909H.Parallel Swaps Sort

Dubmood - Keygen 8

⠀

You are given a permutation $p_1, p_2, \dots, p_n$ of $[1, 2, \dots, n]$. You can perform the following operation some (possibly $0$) times:

• choose a subarray $[l, r]$ of even length;
• swap $a_l$, $a_{l+1}$;
• swap $a_{l+2}$, $a_{l+3}$ (if $l+3 \leq r$);
• $\dots$
• swap $a_{r-1}$, $a_r$.

Sort the permutation in at most $10^6$ operations. You do not need to minimize the number of operations.

Dubmood - Keygen 8

⠀

给你一个 $[1, 2, \dots, n]$ 的排列 $p_1, p_2, \dots, p_n$。你可以执行以下操作若干次（可以为 $0$ 次）：

• 选择一个长度为偶数的子数组 $[l, r]$；
• 交换 $a_l$ 与 $a_{l+1}$；
• 交换 $a_{l+2}$ 与 $a_{l+3}$（若 $l+3 \leq r$）；
• $\dots$
• 交换 $a_{r-1}$ 与 $a_r$。

请在至多 $10^6$ 次操作内将该排列排序。你无需最小化操作次数。

The first line contains a single integer $n$ ($2 \le n \le 3 \cdot 10^5$) — the length of the permutation.

The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, the $p_i$ are distinct) — the permutation before performing the operations.

第一行包含一个整数 $n$（$2 \le n \le 3 \cdot 10^5$）—— 排列的长度。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$，且所有 $p_i$ 互不相同）—— 执行操作前的排列。

Output your operations in the following format.

The first line should contain an integer $k$ ($0 \le k \le 10^6$) — the number of operations.

The next $k$ lines represent the $k$ operations in order. Each of these $k$ lines should contain two integers $l$ and $r$ ($1 \leq l \lt r \leq n$, $r-l+1$ must be even) — the corresponding operation consists in choosing the subarray $[l, r]$ and swapping its elements according to the problem statement.

After all the operations, $a_i = i$ must be true for each $i$ ($1 \leq i \leq n$).

请按以下格式输出你的操作。

第一行应包含一个整数 $k$（$0 \le k \le 10^6$）—— 表示操作的总数。

接下来的 $k$ 行依次表示这 $k$ 个操作。每行应包含两个整数 $l$ 和 $r$（$1 \leq l \lt r \leq n$，且 $r-l+1$ 必须为偶数）—— 对应的操作即为选择子数组 $[l, r]$，并按照题目描述的方式交换其元素。

所有操作完成后，必须满足对每个 $i$（$1 \leq i \leq n$）均有 $a_i = i$。

In the first test:

• At the beginning, $p = [2, 5, 4, 1, 3]$.
• In the first operation, you can choose $[l, r] = [1, 4]$. Then, $(a_1, a_2)$ are swapped and $(a_3, a_4)$ are swapped. The new permutation is $p = [5, 2, 1, 4, 3]$.
• In the second operation, you can choose $[l, r] = [1, 2]$. Then, $(a_1, a_2)$ are swapped. The new permutation is $p = [2, 5, 1, 4, 3]$.
• In the third operation, you can choose $[l, r] = [2, 5]$. Then, $(a_2, a_3)$ are swapped and $(a_4, a_5)$ are swapped. The new permutation is $p = [2, 1, 5, 3, 4]$.
• In the fourth operation, you can choose $[l, r] = [1, 4]$. Then, $(a_1, a_2)$ are swapped and $(a_3, a_4)$ are swapped. The new permutation is $p = [1, 2, 3, 5, 4]$.
• In the fifth operation, you can choose $[l, r] = [4, 5]$. Then, $(a_4, a_5)$ are swapped. The new permutation is $p = [1, 2, 3, 4, 5]$, which is sorted.

In the second test, the permutation is already sorted, so you do not need to perform any operation.

在第一个测试用例中：

• 初始时，$p = [2, 5, 4, 1, 3]$。
• 在第一次操作中，可选择区间 $[l, r] = [1, 4]$。此时，$(a_1, a_2)$ 被交换，且 $(a_3, a_4)$ 被交换。得到的新排列为 $p = [5, 2, 1, 4, 3]$。
• 在第二次操作中，可选择区间 $[l, r] = [1, 2]$。此时，$(a_1, a_2)$ 被交换。得到的新排列为 $p = [2, 5, 1, 4, 3]$。
• 在第三次操作中，可选择区间 $[l, r] = [2, 5]$。此时，$(a_2, a_3)$ 被交换，且 $(a_4, a_5)$ 被交换。得到的新排列为 $p = [2, 1, 5, 3, 4]$。
• 在第四次操作中，可选择区间 $[l, r] = [1, 4]$。此时，$(a_1, a_2)$ 被交换，且 $(a_3, a_4)$ 被交换。得到的新排列为 $p = [1, 2, 3, 5, 4]$。
• 在第五次操作中，可选择区间 $[l, r] = [4, 5]$。此时，$(a_4, a_5)$ 被交换。得到的新排列为 $p = [1, 2, 3, 4, 5]$，即已排序。

在第二个测试用例中，排列本身已有序，因此无需执行任何操作。