心算能力(Arithmetic Ability)
题目描述
Charlie 和 David 正在进行一场记忆力与心算能力的比赛。
比赛开始时,他们面前有一个长度为 n 的整数数组 {a1,a2,…,an},其中所有元素的初始值均为 0。
接下来,他们将依次进行 m 次操作。每次操作为以下两种类型之一:
∙修改操作:给定四个整数 l,r,o,y,对区间 [l,r] 中的每一个元素,根据其当前的奇偶性进行修改。其中:
∘若 o=0,则将区间内所有偶数增加 y,奇数保持不变;
∘若 o=1,则将区间内所有奇数增加 y,偶数保持不变。
∙查询操作:给定两个整数 l,r,计算并输出区间 [l,r] 中所有元素的和,即 i=l∑rai。
需要注意,修改操作中元素的奇偶性以本次操作执行前的数值为准。每次修改完成后,数组中的元素可能发生奇偶性变化,后续操作应当基于修改后的数组进行。
现在,请你按照给定的顺序执行所有操作,并回答每一次查询。
输入格式
第一行输入两个整数 n,m(1≦n,m≦5×105),分别表示数组的长度和操作次数。
注意,输入中不包含初始数组,数组的 n 个元素初始时全部为 0。
此后 m 行,第 i 行先输入一个整数 fi(0≦fi≦1) 表示操作类型。随后在同一行上:
∙若 fi=0,输入四个整数 $l_i, r_i, o_i, y_i \left(1 \leqq l_i \leqq r_i \leqq n;\ 0 \leqq o_i \leqq 1;\ -10^9 \leqq y_i \leqq 10^9\right)$,表示对区间 [li,ri] 执行一次修改操作。其中,oi=0 表示修改偶数,oi=1 表示修改奇数,yi 表示增加的数值;
∙若 fi=1,输入两个整数 $l_i, r_i \left(1 \leqq l_i \leqq r_i \leqq n\right)$,表示查询区间 [li,ri] 的元素和。
保证在整个操作过程中,数组中任意元素的绝对值,以及任意连续区间内元素和的绝对值,均不超过 1018。
输出格式
对于每一次查询操作,新起一行,输出一个整数,表示对应区间内所有元素的和。
若不存在查询操作,则不需要输出任何内容。
测试样例
5 4
0 2 5 0 15
0 1 3 0 40
1 1 5
1 2 4
100
45
样例 1 解释
初始时,数组为 {0,0,0,0,0}。
∙第一次操作,将区间 [2,5] 中所有偶数增加 15。由于初始时所有元素均为偶数,修改后的数组为 {0,15,15,15,15};
∙第二次操作,将区间 [1,3] 中所有偶数增加 40。此时区间内只有 a1=0 是偶数,因此修改后的数组为 {40,15,15,15,15};
∙第三次操作,查询区间 [1,5] 的元素和,得到 40+15+15+15+15=100;
∙第四次操作,查询区间 [2,4] 的元素和,得到 15+15+15=45。
6 7
0 1 6 0 3
0 2 5 1 -4
1 1 6
0 3 6 1 1
1 2 6
0 1 4 0 -2
1 1 4
2
3
-2
样例 2 解释
初始时,数组为 {0,0,0,0,0,0}。
∙第一次操作,将区间 [1,6] 中所有偶数增加 3,得到 {3,3,3,3,3,3};
∙第二次操作,将区间 [2,5] 中所有奇数减少 4,得到 {3,−1,−1,−1,−1,3};
∙第三次操作,查询区间 [1,6] 的元素和,得到 3−1−1−1−1+3=2;
∙第四次操作,将区间 [3,6] 中所有奇数增加 1,得到 {3,−1,0,0,0,4}。注意,原本为奇数的元素在增加 1 后变成了偶数;
∙第五次操作,查询区间 [2,6] 的元素和,得到 −1+0+0+0+4=3;
∙第六次操作,将区间 [1,4] 中所有偶数减少 2,得到 {3,−1,−2,−2,0,4};
∙第七次操作,查询区间 [1,4] 的元素和,得到 3−1−2−2=−2。