[AdditionalFile5221.zip](file://AdditionalFile5221.zip?type=additional_file)

#5221. 「UOI 2023 Stage 4 Day1」数组与部分和

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2023 Stage 4 Day1 T4. Масив і часткові суми

对于一个长度为 $n$ 的整数数组 $a$，其前缀和数组是一个长度为 $n$ 的数组 $b$，其中 $b_i = a_1 + a_2 + \ldots + a_i$。

对于一个长度为 $n$ 的整数数组 $a$，其后缀和数组是一个长度为 $n$ 的数组 $b$，其中 $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。第二类和第三类操作的描述格式分别为 2 l 和 3 l r，其中 $l$ 和 $r$ $(1 \le l \le r \le n)$ 表示当前操作子区间的左边界和右边界。

如果存在多个正确答案，可以输出任意一个。

样例

输入

7 0
0 0 1 -1 -1 -1 1

输出

2
3 1 3
2 1 7

在第一个样例中，数组 $a$ 经历了两次变化：

1. 执行第三类操作，参数为 $l=1$，$r=3$，数组 $a$ 变为 $[1, 1, 1, -1, -1, -1, 1]$；
2. 执行第二类操作，参数为 $l=1$，$r=7$，数组 $a$ 变为 $[1, 2, 3, 2, 1, 0, 1]$。

数据范围与提示

设对于某个测试点，所需的最小操作次数为 $m_{ans}$，而你的解决方案使用的操作次数为 $m_{user}$。

详细子任务附加限制及分值如下表所示：