presuffix

题目信息

时间限制: 4s

空间限制: 512M

输入文件: presuffix.in

输出文件: presuffix.out

题目描述

数组 $x_1,x_2,\cdots,x_k$ 的前缀和数组 $y_1,y_2,\cdots,y_k$ 满足 $y_i =x_1+x_2+\cdots+x_i$，后缀和数组 $z_1,z_2,\cdots,z_k$ 满足 $z_i=x_k+x_{k-1}+\cdots+x_i$。

给定整数数组 $a_1,a_2,\cdots,a_{N}$，可以为负。有三种操作：

1. 将每个元素乘上 $-1$，即变为它们的相反数。
2. 选择 $a$ 的一个区间 $[l,r]$，将 $a_l,a_{l+1},\cdots,a_{r}$ 替换成当前 $a_l,a_{l+1},\cdots,a_{r}$ 的前缀和数组。
3. 选择 $a$ 的一个区间 $[l,r]$，将 $a_l,a_{l+1},\cdots,a_{r}$ 替换成当前 $a_l,a_{l+1},\cdots,a_{r}$ 的后缀和数组。

每一次操作完后，对于所有数 $a_i$，将 $a_i$ 变为 $\max\{\min\{a_i,10^{18}\},-10^{18}\}$。

请你最小化操作的次数，使得 $a$ 中所有元素变得非负。

输入格式

第一行两个正整数 $N,id$，其中 $id$ 表示子任务编号，对于样例，$id=0$。

第二行 $N$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

第一行一个非负整数 $K$ 表示操作次数。

接下来 $K$ 行，每行形如：

• $1$
• $2 \space l \space r$
• $3 \space l \space r$

表示操作种类和 $2,3$ 类操作的操作区间。

本题存在 SPJ，请参见“数据范围与约定”。

样例

样例输入 #1

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

样例输出 #1

2
3 1 3
2 1 7

样例解释 #1

第一次操作完，$a=1,1,1,-1,-1,-1,1$。

第二次操作完，$a=1,2,3,2,1,0,1$。

数据范围与提示

对于所有数据，有：

• $1 \le n \le 2 \times 10^5$
• $-1 \le a_i \le 1$。

本题存在 SPJ，对于某个子任务，令 $K_1$ 为你的操作次数，$K_2$ 为最小的操作次数，若 $K_1-K_2 \le lim$，则你的输出被认为是正确的，$lim$ 对于每个子任务均不同。