P16525 一如陌上尘

>或真亦或伪？飘如陌上尘。

对于长度为 $n$ 的序列 $a$，有以下三种操作： - 选定两个数 $1\le l\le r\le n$，使得 $a_{l\sim r}$ 减一，消耗一点代价。 - 选定一个数 $1\le k\le n$，使得 $a_{k\sim n}$ 减一，不消耗代价。 - 选定一个数 $1\le k\le n$，使得 $a_{1\sim k}$ 减一，不消耗代价。 需要通过若干次操作将 $a$ 的每个元素变为同一个非负整数 $p$，设消耗的总代价为 $m$。记 $f(a)$ 为所有可行方案中 $m-p$ 的最小值。 有一个长为 $n$ 的序列 $v$，有 $q$ 次操作，每次为其中之一： 1. 修改操作。给出三个数 $l,r,x$，将 $v_{l\sim r}$ 修改为 $x$。 2. 询问操作。给出两个数 $l,r$，询问所有长度为 $r-l+1$，满足 $0\le a_i\le v_{i+l-1}$ 的序列 $a$，其 $f(a)$ 的和。

第一行输入两个数 $n,q$。 第二行输入 $n$ 个数，第 $i$ 个数表示 $v_i$。 接下来 $q$ 行，第一个数为 $op\in [1,2]$ 表示操作类型，若 $op=1$，接下来输入三个数 $l,r,x$，表示一次修改；否则输入两个数 $l,r$，表示一次询问。

输出若干行，对应每次询问的答案，对 $10^9+7$ 取模。

**本题 I/O 量较大，请使用较快的 I/O 方式。** ### 样例解释： 对于第一个询问，序列 $a$ 可以为 $\{0,0\},\{0,1\},\{0,2\},\{1,0\},\{1,1\},\{1,2\}$，$f(a)$ 分别为 $0,0,0,0,-1,-1$，和为 $-2$，在模 $10^9+7$ 意义下为 $1000000005$。 ### 数据范围： | Subtask |分值 | $n \le$ | $q \le$ | $v_i \le$ | $x \le$ | 特殊性质 | |:-:|:-:|:-:|:-:|:-:|:-:|:-:| | $1$ |$ 20$ | $10$ | < | $3$ | < | 无 | | $ 2 $ |$ 15$ | $200$ | < | $500$ | < | ^ | |$ 3$ |$ 5$ | $2 \times 10^3$ | < | $10^9$ | < | A| | $ 4$ | $ 15 $ | ^ | ^ | ^ | ^ | 无 | | $ 5$ |$ 10 $ | $2\times 10^4$ |< |^|^|B| | $ 6$ | $ 15$ | $2 \times 10^5$ | < | ^ | ^ | ^ | | $ 7 $ | $ 20$ | ^ | ^ | ^ | ^ | 无 | 对于 $100\%$ 的数据，保证： $2\le n\le 2\times 10^5$，$1\le q\le 2\times 10^5$，$0\le v_i,x\le 10^9$，$1\le l