P12569 [UOI 2023] An Array and Partial Sums

对于一个长度为 $n$ 的整数数组 $a$，其**前缀和数组** $b$ 定义为长度为 $n$ 的数组，其中 $b_i = a_1 + a_2 + \ldots + a_i$。 对于一个长度为 $n$ 的整数数组 $a$，其**后缀和数组** $b$ 定义为长度为 $n$ 的数组，其中 $b_i = a_n + a_{n-1} + \ldots + a_i$。 我们定义整数数组 $a$ 的**标准化**操作为：对于 $1 \le i \le n$，执行赋值 $a_i \leftarrow \max(\min(a_i, 10^{18}), -10^{18})$。 给定一个长度为 $n$ 的整数数组 $a$。 允许执行以下三种类型的操作： 1. 将数组 $a$ 的每个元素取相反数（即对 $1 \le i \le n$ 执行赋值 $a_i \leftarrow (-a_i)$）； 2. 选择数组 $a$ 的任意子段，并用其前缀和数组替换该子段，然后对数组 $a$ 进行**标准化**； 3. 选择数组 $a$ 的任意子段，并用其后缀和数组替换该子段，然后对数组 $a$ 进行**标准化**。 找到使数组 $a$ 的所有元素变为非负数的最短操作序列。 注意：对于某些测试用例组，允许输出的操作序列不一定是最短的。

第一行包含两个整数 $n$ 和 $g$（$1 \le n \le 2 \cdot 10^5$，$0 \le g \le 8$）——分别表示数组的长度和测试用例组编号。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-1 \le a_i \le 1$）——数组的元素。

第一行输出一个整数 $m$ —— 使数组 $a$ 的所有元素变为非负数所需的最小操作次数。 接下来的 $m$ 行，每行输出一个操作的描述： - 对于类型 1 的操作，输出格式为 `1`； - 对于类型 2 的操作，输出格式为 `2 l r`，其中 $l$ 和 $r$（$1 \le l \le r \le n$）表示操作子段的左右边界； - 对于类型 3 的操作，输出格式为 `3 l r`，其中 $l$ 和 $r$ 的定义同上。 如果存在多个正确答案，输出任意一个均可。

在第一个样例中，数组 $a$ 的变化如下： 1. 执行类型 3 的操作，参数为 $l=1$、$r=3$ 后，数组变为 $[1, 1, 1, -1, -1, -1, 1]$； 2. 执行类型 2 的操作，参数为 $l=1$、$r=7$ 后，数组变为 $[1, 2, 3, 2, 1, 0, 1]$。 ### 评分标准 设某测试用例的最短操作次数为 $m_{ans}$，你的解使用的操作次数为 $m_{user}$。 - （$14$ 分）：$m_{ans} \le 1$； - （$17$ 分）：若 $m_{user} \le 100$ 则视为正确。可以证明在给定约束下总存在不超过 $100$ 次操作的解； - （$18$ 分）：若 $m_{user} \le m_{ans} + 3$ 则视为正确； - （$7$ 分）：若 $m_{user} \le m_{ans} + 1$ 则视为正确； - （$7$ 分）：$n \le 3000$，且保证**所有**最短操作序列**仅包含**类型 2 的操作； - （$19$ 分）：保证**所有**最短操作序列**仅包含**类型 2 的操作； - （$17$ 分）：$n \le 3000$； - （$1$ 分）：无额外限制。 翻译由 DeepSeek V3 完成