P11334 [NOISG 2020 Finals] Progression

Damian 正在开发一款视频游戏！

该游戏包含 $N$ 个任务，第 $i$ 个任务的初始难度为 $D_i$。为了让玩家感受到难度的渐进性，Damian 对任务难度进行了若干次调整操作。 游戏设计支持两种操作： 1. **补丁操作**：将任务 $L$ 到 $R$ 的难度按公式 $D_i = D_i + S + (i - L) \times C$ 增加。 2. **重写操作**：将任务 $L$ 到 $R$ 的难度直接设置为 $D_i = S + (i - L) \times C$。 为了让游戏更加有趣，Damian 希望找到任务的连续子序列，使它们的难度呈等差数列。玩家可以按顺序或倒序完成任务。任务 $a$ 到 $b$ ($1 \leq a \leq b \leq N$) 构成可玩子段当且仅当对所有 $a \leq i < b$，满足 $D_{i+1} - D_i = k$（$k$ 为某个整数，可以为负）。单个任务也构成长度为 $1$ 的可玩子段。 Damian 有时需要回答一个查询：找出某一区间内最长的可玩子段长度。你需要帮助 Damian 处理这些查询。

- 第一行包含两个整数 $N$ 和 $Q$，分别表示任务的数量和操作与查询的总数。 - 第二行包含 $N$ 个整数，表示任务的初始难度 $D_1, D_2, \dots, D_N$。 - 接下来的 $Q$ 行描述操作或查询： - 若行首为 $1$，接下来为 $L, R, S, C$，表示补丁操作。 - 若行首为 $2$，接下来为 $L, R, S, C$，表示重写操作。 - 若行首为 $3$，接下来为 $L, R$，表示查询操作。

对于每个查询操作，输出一个整数，表示指定区间内最长的可玩子段长度。

【样例解释】 对于样例 #1： - 第一次查询时，任务 $5$ 到 $9$ 构成最长可玩子段。 - 第一次补丁操作后，任务难度变为 $[0, 0, 0, 0, 1, 2, 3, 4, 5, 5]$。 第二次查询时，任务 $4$ 到 $9$ 构成最长可玩子段。 - 第二次补丁操作后，任务难度变为 $[0, 0, 0, 0, -2, -4, -6, -8, -10, -12]$。 最后一次查询时，任务 $4$ 到 $10$ 构成最长可玩子段。 【数据范围】 - $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$ | 子任务编号 | 分值 | 限制条件 | |:---:|:---:|:---:| | $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$ | 无额外限制。 |