CF2271F Beautiful Pillers

对于一个长度为 $m$ 的整数数组 $b$，如果一对下标 $(l, r)$（$l < r$）满足 $b_l = b_r$，且不存在下标 $i$（$l < i < r$）使得 $b_i \geq b_l$，则称这对下标是“好对”。 如果某个下标 $i$ 满足 $l \leq i \leq r$，并且 $(l, r)$ 是“好对”，我们称下标 $i$ 被该“好对”覆盖。 如果数组 $b$ 的每一个下标都至少被一对“好对”覆盖，那么称 $b$ 是“美丽”的。 现在给定一个长度为 $n$ 的整数数组 $a$。你可以对它进行如下操作：选择两个整数 $i$ 和 $x$（$1 \leq i \leq n$，$1 \leq x \leq 10^9$），然后将 $a_i = x$。 请你求出使数组 $a$ 变成“美丽”所需的最少操作次数，并输出具体的操作过程。可以证明，最多 $n$ 次操作一定能完成任务。

每组测试数据包含多组测试用例。第一行包含测试用例组数 $t$（$1 \leq t \leq 10^4$）。 接下来依次描述每组测试用例： 每组测试用例的第一行包含整数 $n$（$2 \leq n \leq 2 \times 10^5$），表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示数组 $a$。 保证所有测试用例中的 $n$ 之和不超过 $2 \times 10^5$。

对于每组测试用例，输出一行包含整数 $k$（$0 \leq k \leq n$），表示需要的最小操作次数。 接下来输出 $k$ 行，每行包含两个整数 $i$ 和 $x$（$1 \leq i \leq n$，$1 \leq x \leq 10^9$），表示一次操作：将 $a_i$ 赋值成 $x$。 如果存在多种最优方案，输出任意一种即可。

在第一个样例中，原数组 $a = [1, 2, 3]$ 没有任何“好对”，因此不是美丽的。执行一次操作 $i = 1, x = 3$，变为 $[3, 2, 3]$，此时对 $(1, 3)$ 是“好对”，能覆盖全部三个下标。 在第二个样例中，原数组 $a = [5, 3, 2, 5, 1, 7, 9, 9]$ 只有 $(1, 4)$ 和 $(7, 8)$ 两对“好对”，下标 $5$ 和 $6$ 没有被覆盖。执行一次操作 $i = 5, x = 7$，得到 $[5, 3, 2, 5, 7, 7, 9, 9]$，除了原有的两对“好对”，又新增了 $(5, 6)$，成功覆盖所有下标。 在第三个样例中，原数组已经是美丽的，因为对于每个 $i$（$1 \leq i \leq 4$），$(i, i+1)$ 都是“好对”。因此不需要任何操作。 由 ChatGPT 5 翻译