#PQJ1854x9634. QOJ 1854_9634
QOJ 1854_9634
标题: 序列 - Problem - QOJ.ac
#9634. 序列
The problem was used in the following contests:
题目描述
已知一个序列 a 和一个初值为 0 的序列 b,你需要进行下面三种操作:
1 x y:将 ax 修改为 y。2 l r:对于所有的 i∈[l,r],将 bi 加上 maxij=laj。3 l r:求 ∑ri=lbi。
输入格式
第一行包含两个正整数 n,m,分别表示序列 a 的长度和操作次数。
第二行包含 n 个整数 a1,a2,⋯,an,表示序列 a。
接下来 m 行,每行行首有一个整数 op,表示操作类型,接下来两个整数表示操作参数。
输出格式
对于 op=3 的操作,输出一行包含一个整数,表示这个询问的答案。
样例输入 1
5 5
2 1 4 3 5
2 1 3
2 4 3
1 2 3
3 1 3
3 2 5
样例输出 1
8
6
样例输入 2
10 10
5 6 10 3 6 7 10 10 1 10
2 2 4
1 10 7
3 2 8
2 4 5
1 8 2
3 2 2
2 8 9
2 1 2
1 2 10
3 2 3
样例输出 2
26
6
22
数据范围
对于 100% 的数据,保证 1≤n,m≤5×105, 1≤l≤r≤n,1≤x≤n,1≤ai,y≤109。
子任务编号 n,m≤ 分值 特殊性质 1 1000 5 无 2 105 15 3 2×105 20 4 5×105 20 当 op=2 时,l=1。 5 20 op≠1 6 20 无