QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
[+1]

# 3272. 简单数据结构

Statistics

小 D 是一位数据结构大师,他特别喜欢研究形式简单的数据结构,今天他想到了这样一道题目:

你有一个长度为 n 的序列 a,下面你要进行 q 次修改或询问。

  1. 给定 v,将所有 ai 变为 min

  2. 将所有 a_i 变为 a_i + i

  3. 给定 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。

输出格式

若干行,每行一个整数表示答案。

样例数据

样例输入

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

样例输出

33
9
107

数据范围与提示

子任务编号 子任务分值 n, q\leq 特殊性质
1 10 5000
2 20 200000 A
3 15 op_i\neq 2
4 55

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] 在所有可行区间随机生成。