题目描述

对于一个长度为 $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$ 的定义同上。

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

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

2
3 1 3
2 1 7

提示

在第一个样例中，数组 $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 完成