P8987 [北大集训 2021] 简单数据结构

CTT2021 D2T1

小 D 是一位数据结构大师，他特别喜欢研究形式简单的数据结构，今天他想到了这样一道题目： 你有一个长度为 $n$ 的序列 $a$，下面你要进行 $q$ 次修改或询问。 1. 给定 $v$，将所有 $a_i$ 变为 $\min(a_i, v)$。 2. 将所有 $a_i$ 变为 $a_i + i$。 3. 给定 $l, r$，询问 $\sum_{i=l}^r a_i$。 顶级数据结构大师小 D 轻松的解决了这个问题，现在他打算来考考即将参加 IOI2022 的你，相信你也可以轻松解决这个问题。

无

无

| 子任务编号 | 子任务分值 | $n,q$ | 特殊性质 | | :--------: | :--------: | :------: | :----------: | | $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]$ 在所有可行区间随机生成。