#2055. 简单数据结构
简单数据结构
简单数据结构
题目描述
标题: 简单数据结构 - Problem - QOJ.ac
The problem was used in the following contests:
小 D 是一位数据结构大师,他特别喜欢研究形式简单的数据结构,今天他想到了这样一道题目:
你有一个长度为 n 的序列 a,下面你要进行 q 次修改或询问。
- 给定 v,将所有 ai 变为 min(ai,v)。
- 将所有 ai 变为 ai+i。
- 给定 l,r,询问 ∑i=lrai。
顶级数据结构大师小 D 轻松的解决了这个问题,现在他打算来考考即将参加 IOI2022 的你,相信你也可以轻松解决这个问题。
输入格式
第一行两个正整数 n,q 表示序列的长度与修改/询问的个数。
下面一行 n 个整数 ai,表示初始序列 a。
下面 q 行,每行第一个正整数 opi 表示第 i 次修改/询问的类型。
若 opi=1,则下面紧跟一个整数 vi,表示进行一次修改 1。
若 opi=2,则表示进行一次修改 2。
若 opi=3,则下面紧跟两个正整数 li,ri,表示进行一次询问 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≤ 特殊性质 1 10 5000 2 20 200000 A 3 15 opi≠2 4 55
1≤n,q≤2×105,0≤ai,vi≤1012
性质 A 为:ai,vi 在 [0,1012] 随机生成,opi 在 [1,3] 随机生成,[li,ri] 在所有可行区间随机生成。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
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