CF2271F.Beautiful Pillers

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

For an array bb of mm integers, a pair of indices (l,r)(l, r) (l<rl \lt r) is called good if bl=brb_l = b_r and there is no index ii (l<i<rl \lt i \lt r) such that bi≥blb_i \ge b_l.

We say that an index ii is covered by a good pair (l,r)(l, r) if l≤i≤rl \le i \le r.

The array bb is called beautiful if every index is covered by at least one good pair.

You are given an array aa of nn integers. You can perform the following operation with it: choose two integers ii and xx (1≤i≤n1 \le i \le n, 1≤x≤1091 \le x \le 10^9) and set ai=xa_i = x.

Find the minimum number of operations required to make the array beautiful. Also, output the operations. It can be shown that it is always possible to make the array beautiful using at most nn operations.

对于一个包含 mm 个整数的数组 bb,若一对下标 (l,r)(l, r)(满足 l<rl \lt r)满足 bl=brb_l = b_r,且不存在下标 ii(满足 l<i<rl \lt i \lt r)使得 bi≥blb_i \ge b_l,则称该对下标为好对。

若下标 ii 满足 l≤i≤rl \le i \le r,则称其被好对 (l,r)(l, r) 覆盖。

若数组 bb 的每个下标均至少被一个好对覆盖,则称该数组为优美的。

给定一个包含 nn 个整数的数组 aa。你可以对其执行如下操作:选择两个整数 ii 和 xx(其中 1≤i≤n1 \le i \le n,1≤x≤1091 \le x \le 10^9),并将 aia_i 赋值为 xx。

请找出使数组变为优美的最少操作次数,并输出所有操作。可以证明:至多使用 nn 次操作总能使数组变为优美。

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041 \le t \le 10^4). The description of the test cases follows.

The first line of each test case contains a single integer nn (2≤n≤2⋅1052 \le n \le 2 \cdot 10^5) — the length of the array aa.

The second line of each test case contains nn integers a1,a2,…,ana_1, a_2, \ldots, a_n (1≤ai≤1091 \le a_i \le 10^9) — the array aa.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052 \cdot 10^5.

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1041 \le t \le 10^4)。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 nn(2≤n≤2⋅1052 \le n \le 2 \cdot 10^5)—— 数组 aa 的长度。

每个测试用例的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n(1≤ai≤1091 \le a_i \le 10^9)—— 数组 aa。

保证所有测试用例中 nn 的总和不超过 2⋅1052 \cdot 10^5。

输出格式

For each test case, output a single integer kk (0≤k≤n0 \le k \le n) — the minimum number of operations.

Then output kk lines describing the operations in the order they are applied. Each of these lines should contain two integers ii and xx (1≤i≤n1 \le i \le n, 1≤x≤1091 \le x \le 10^9) — the index and the new value of the corresponding operation.

If there are multiple optimal sequences of operations, output any of them.

对于每个测试用例,输出一个整数 kk(0≤k≤n0 \le k \le n)——即最少操作次数。

然后输出 kk 行,按操作执行顺序描述这些操作。每行应包含两个整数 ii 和 xx(1≤i≤n1 \le i \le n,1≤x≤1091 \le x \le 10^9)——分别表示操作的下标和对应的新值。

如果存在多个最优操作序列,输出其中任意一个即可。

输入输出样例

  • 输入#1

    5
    3
    1 2 3
    8
    5 3 2 5 1 7 9 9
    5
    1 1 1 1 1
    8
    1 2 3 4 4 3 2 1
    2
    1000000000 1000000000

    输出#1

    1
    1 3
    1
    5 7
    0
    2
    1 3
    8 3
    0

说明/提示

In the first example, the array a=[1,2,3]a = [1, 2, 3] has no good pairs at all, so it is not beautiful. After the operation with i=1i = 1 and x=3x = 3, the array becomes [3,2,3][3, 2, 3]. The pair (1,3)(1, 3) is good because its endpoints are both 33 and its only internal value is 2<32 \lt 3, so it covers all three indices.

In the second example, the array a=[5,3,2,5,1,7,9,9]a = [5, 3, 2, 5, 1, 7, 9, 9] has exactly two good pairs, (1,4)(1, 4) and (7,8)(7, 8), so the indices 55 and 66 are not covered. The operation with i=5i = 5 and x=7x = 7 turns the array into [5,3,2,5,7,7,9,9][5, 3, 2, 5, 7, 7, 9, 9]: the pairs (1,4)(1, 4) and (7,8)(7, 8) are still good, and the new good pair (5,6)(5, 6) covers the two remaining indices.

In the third example, the array is already beautiful, since (i,i+1)(i, i + 1) is a good pair for every ii from 11 to 44. Therefore, no operations are needed.

在第一个例子中,数组 a=[1,2,3]a = [1, 2, 3] 完全不存在好对(good pair),因此它不是优美的(beautiful)。执行操作 i=1i = 1、x=3x = 3 后,数组变为 [3,2,3][3, 2, 3]。此时,数对 (1,3)(1, 3) 是一个好对,因为其两个端点值均为 33,且其唯一内部元素为 2<32 \lt 3,从而覆盖了全部三个下标。

在第二个例子中,数组 a=[5,3,2,5,1,7,9,9]a = [5, 3, 2, 5, 1, 7, 9, 9] 恰好包含两个好对:(1,4)(1, 4) 和 (7,8)(7, 8),因此下标 55 和 66 未被覆盖。执行操作 i=5i = 5、x=7x = 7 后,数组变为 [5,3,2,5,7,7,9,9][5, 3, 2, 5, 7, 7, 9, 9]:原有的好对 (1,4)(1, 4) 和 (7,8)(7, 8) 依然成立,同时新增的好对 (5,6)(5, 6) 覆盖了剩余的两个下标。

在第三个例子中,该数组本身已是优美的,因为对每个从 11 到 44 的 ii,数对 (i,i+1)(i, i + 1) 均为好对。因此,无需执行任何操作。

输入解题思路,AI测评打分。不知道怎么写?

首页