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

#5244. 「NOISG 2020 Final」Progression

标签: 传统 | 时间限制: 3000 ms | 内存限制: 1024 MiB |

题目描述

译自 NOISG 2020 Final T3. Progression

达米安正在开发一款视频游戏！游戏包含 $N$ 个任务，第 $i$ 个任务初始难度为 $D_i$。这款游戏采用了最先进的游戏设计，可以正向或反向游玩。当然，确保玩家感受到进程感非常重要——难度应持续递增。因此，达米安执行了一系列操作。

他执行的操作有两种类型。第一种是补丁操作，由四个整数 $L, R, S, C$ 定义，表示对于 $L \leq i \leq R$ 的任务 $i$，其难度 $D_i$ 将增加 $S + (i - L) \times C$。

第二种是重写操作，同样由四个整数 $L, R, S, C$ 定义，表示对于 $L \leq i \leq R$ 的任务 $i$，其难度 $D_i$ 将被设置为 $S + (i - L) \times C$。

达米安决定，只有当一段连续的任务序列的难度以恒定速率变化时，这段序列才构成一个可玩片段（毕竟，玩家可以选择反向游玩）！换句话说，任务 $a$ 到 $b$（其中 $1 \leq a \leq b \leq N$）构成一个可玩片段，当且仅当对于所有 $a \leq i < b$，$D_{i+1} - D_i = k$，其中 $k$ 是一个整数（可能 $k \leq 0$）。单个任务本身构成一个长度为 $1$ 的可玩片段。

达米安会不时执行一个评估查询，由两个整数 $L$ 和 $R$ 定义，表示他想知道在当前时刻，任务 $L$ 到 $R$ 之间最长可玩片段的长度。

然而，达米安的操作并不一定能改善游戏体验。因此，他需要你的帮助来回答这些查询，以便开发出最佳的游戏。

输入格式

程序需从标准输入读取数据。

第一行包含两个整数 $N$ 和 $Q$，分别表示任务数量和操作及查询的总数。

第二行包含 $N$ 个空格分隔的整数 $D_1, \ldots, D_N$，表示初始难度。

接下来的 $Q$ 行，每行表示一个操作或查询：

• 如果行以整数 $1$ 开头，接下来的 $4$ 个整数为 $L, R, S, C$，表示补丁操作。
• 如果行以整数 $2$ 开头，接下来的 $4$ 个整数为 $L, R, S, C$，表示重写操作。
• 如果行以整数 $3$ 开头，接下来的 $2$ 个整数为 $L, R$，表示评估查询。

输出格式

程序需向标准输出输出结果。

对于每个评估查询，输出一行，包含一个整数，表示当前时刻任务 $L$ 到 $R$ 之间最长可玩片段的长度。

样例 1

输入

10 6
1 2 3 4 1 2 3 4 5 5
3 1 10
1 1 4 -1 -1
3 1 10
3 9 10
2 5 10 -2 -2
3 1 10

输出

5
6
2
7

对于第一个评估查询，任务 $5$ 到 $9$ 构成最长可玩片段（$k=1$）。

在补丁操作后，难度变为 $[0, 0, 0, 0, 1, 2, 3, 4, 5, 5]$。

对于第二个评估查询，任务 $4$ 到 $9$ 构成最长可玩片段（$k=1$）。

对于第三个评估查询，任务 $9$ 到 $10$ 构成最长可玩片段（$k=0$），因为仅考虑任务 $L=9$ 到 $R=10$ 之间的任务。

在重写操作后，难度变为 $[0, 0, 0, 0, -2, -4, -6, -8, -10, -12]$。

对于最后一个评估查询，任务 $4$ 到 $10$ 构成最长可玩片段（$k=-2$）。

这个样例满足子任务 $2, 6$ 的限制。

样例 2

输入

10 5
1 2 3 4 1 2 3 4 5 5
3 1 10
1 1 10 1 2
3 1 10
2 1 10 3 4
3 1 10

输出

5
5
10

这个样例满足子任务 $1, 2, 6$ 的限制。

样例 3

输入

10 5
1 2 3 4 1 2 3 4 5 5
3 1 4
3 4 5
3 2 4
3 5 9
3 10 10

输出

4
2
3
5
1

这个样例满足子任务 $2, 3, 4, 5, 6$ 的限制。

样例 4

输入

10 5
1 2 3 4 1 2 3 4 5 5
2 10 10 6 1
3 5 10
1 5 5 4 1
3 1 5
3 1 6

输出

6
5
5

注意，当 $L=R$ 时，$C$ 不一定为 $0$，但其值对操作无影响。

这个样例满足子任务 $2, 4, 6$ 的限制。

样例 5

输入

10 5
1 2 3 4 1 2 3 4 5 5
1 1 4 -1 -1
3 1 5
3 4 5
1 5 10 -1 -1
3 1 10

输出

4
2
9

这个样例满足子任务 $2, 5, 6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N, Q \leq 3 \times 10^5$
• $-10^6 \leq D_i, S, C \leq 10^6$
• $1 \leq L \leq R \leq N$

在给定限制下，$D_i$ 保证在 64 位有符号整数的表示范围内。

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

子任务	分值	附加限制
$1$	$9$	对于所有操作和查询，$L=1, R=N$
$2$	$15$	$1 \leq N, Q \leq 10^3$
$3$	$35$	没有补丁和重写操作
$4$	$11$	对于所有操作，$L=R$
$5$	$13$	没有重写操作
$6$	$17$	无附加限制