小 D 是一位数据结构大师,他特别喜欢研究形式简单的数据结构,今天他想到了这样一道题目:
你有一个长度为 $n$ 的序列 $a$,下面你要进行 $q$ 次修改或询问。
给定 $v$,将所有 $a_i$ 变为 $\min(a_i, v)$。
将所有 $a_i$ 变为 $a_i + i$。
给定 $l, r$,询问 $\sum_{i=l}^r a_i$。
顶级数据结构大师小 D 轻松的解决了这个问题,现在他打算来考考即将参加 IOI2022 的你,相信你也可以轻松解决这个问题。
输入格式
第一行两个正整数 $n, q$ 表示序列的长度与修改/询问的个数。
下面一行 $n$ 个整数 $a_i$,表示初始序列 $a$。
下面 $q$ 行,每行第一个正整数 $op_i$ 表示第 $i$ 次修改/询问的类型。
若 $op_i = 1$,则下面紧跟一个整数 $v_i$,表示进行一次修改 1。
若 $op_i = 2$,则表示进行一次修改 2。
若 $op_i = 3$,则下面紧跟两个正整数 $l_i, r_i$,表示进行一次询问 3。
输出格式
若干行,每行一个整数表示答案。
样例
input
15 15 6 14 14 6 3 6 4 13 10 3 12 5 11 9 6 1 9 1 2 2 2 2 1 11 3 4 6 2 1 6 2 1 9 1 11 1 11 3 4 4 3 2 13
output
33 9 107
数据范围与提示
子任务编号 | 子任务分值 | $n, q\leq$ | 特殊性质 |
---|---|---|---|
$1$ | $10$ | $5000$ | |
$2$ | $20$ | $200000$ | A |
$3$ | $15$ | $200000$ | $op_i\neq 2$ |
$4$ | $55$ | $200000$ |
$1 \leq n, q \leq 2 \times 10^5, 0 \leq a_i, v_i \leq 10^{12}$
性质 A 为:$a_i, v_i$ 在 $[0, 10^{12}]$ 随机生成,$op_i$ 在 $[1, 3]$ 随机生成,$[l_i, r_i]$ 在所有可行区间随机生成。
时间限制:$\texttt{3s}$
空间限制:$\texttt{512MB}$