CSES1735 区间更新与求和
#CS1735. 区间更新与求和
区间更新与求和
题目背景
翻译自 CSES-1735 题。
题目描述
你的任务是维护一个包含 n 个值的数组，并高效地处理以下几种类型的查询：
-
将区间 [a,b][a,b][a,b] 中的每个值增加 x。
-
将区间 [a,b][a,b][a,b] 中的每个值设置为 x。
-
计算区间 [a,b][a,b][a,b] 中的值的和。
输入格式
第一行包含两个整数 n 和 q：分别表示数组的大小和查询的数量。
第二行包含 n 个整数 t1,t2,…,tnt_1,t_2,…,t_nt1,t2,…,tn：表示数组的初始内容。
接下来有 q 行，每行描述一个查询。查询的格式有三种：
-
1 a b x：表示将区间 [a,b][a,b][a,b] 中的每个值增加 x。
-
2 a b x：表示将区间 [a,b][a,b][a,b] 中的每个值设置为 x。
-
3 a b：表示计算区间 [a,b][a,b][a,b] 中的值的和。
输出格式
对于每个类型为 3 的查询，输出该区间内值的和。
样例
6 5
2 3 1 1 5 3
3 3 5
1 2 4 2
3 3 5
2 2 4 5
3 3 5
7
11
15
说明/提示
1≤ti,x≤1061 \leq t_i,x \leq 10^61≤ti,x≤106；