#P0066. 心算能力

心算能力

心算能力(Arithmetic Ability)

题目描述

\hspace{15pt}Charlie 和 David 正在进行一场记忆力与心算能力的比赛。

\hspace{15pt}比赛开始时,他们面前有一个长度为 nn 的整数数组 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},其中所有元素的初始值均为 00。

\hspace{15pt}接下来,他们将依次进行 mm 次操作。每次操作为以下两种类型之一:

∙ \hspace{23pt}\bullet\,修改操作:给定四个整数 l,r,o,yl, r, o, y,对区间 [l,r][l, r] 中的每一个元素,根据其当前的奇偶性进行修改。其中:

∘ \hspace{38pt}\circ\,若 o=0o = 0,则将区间内所有偶数增加 yy,奇数保持不变;

∘ \hspace{38pt}\circ\,若 o=1o = 1,则将区间内所有奇数增加 yy,偶数保持不变。

∙ \hspace{23pt}\bullet\,查询操作:给定两个整数 l,rl, r,计算并输出区间 [l,r][l, r] 中所有元素的和,即 ∑i=lrai\sum\limits_{i=l}^{r} a_i。

\hspace{15pt}需要注意,修改操作中元素的奇偶性以本次操作执行前的数值为准。每次修改完成后,数组中的元素可能发生奇偶性变化,后续操作应当基于修改后的数组进行。

\hspace{15pt}现在,请你按照给定的顺序执行所有操作,并回答每一次查询。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦5×105)n, m \left(1 \leqq n, m \leqq 5 \times 10^5\right),分别表示数组的长度和操作次数。

\hspace{15pt}注意,输入中不包含初始数组,数组的 nn 个元素初始时全部为 00。

\hspace{15pt}此后 mm 行,第 ii 行先输入一个整数 fi(0≦fi≦1)f_i \left(0 \leqq f_i \leqq 1\right) 表示操作类型。随后在同一行上:

∙ \hspace{23pt}\bullet\,若 fi=0f_i = 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][l_i, r_i] 执行一次修改操作。其中,oi=0o_i = 0 表示修改偶数,oi=1o_i = 1 表示修改奇数,yiy_i 表示增加的数值;

∙ \hspace{23pt}\bullet\,若 fi=1f_i = 1,输入两个整数 $l_i, r_i \left(1 \leqq l_i \leqq r_i \leqq n\right)$,表示查询区间 [li,ri][l_i, r_i] 的元素和。

\hspace{15pt}保证在整个操作过程中,数组中任意元素的绝对值,以及任意连续区间内元素和的绝对值,均不超过 101810^{18}。

输出格式

\hspace{15pt}对于每一次查询操作,新起一行,输出一个整数,表示对应区间内所有元素的和。

\hspace{15pt}若不存在查询操作,则不需要输出任何内容。

测试样例

5 4
0 2 5 0 15
0 1 3 0 40
1 1 5
1 2 4
100
45

样例 1 解释

\hspace{15pt}初始时,数组为 {0,0,0,0,0}\{0, 0, 0, 0, 0\}。

∙ \hspace{23pt}\bullet\,第一次操作,将区间 [2,5][2, 5] 中所有偶数增加 1515。由于初始时所有元素均为偶数,修改后的数组为 {0,15,15,15,15}\{0, 15, 15, 15, 15\};

∙ \hspace{23pt}\bullet\,第二次操作,将区间 [1,3][1, 3] 中所有偶数增加 4040。此时区间内只有 a1=0a_1 = 0 是偶数,因此修改后的数组为 {40,15,15,15,15}\{40, 15, 15, 15, 15\};

∙ \hspace{23pt}\bullet\,第三次操作,查询区间 [1,5][1, 5] 的元素和,得到 40+15+15+15+15=10040+15+15+15+15=100;

∙ \hspace{23pt}\bullet\,第四次操作,查询区间 [2,4][2, 4] 的元素和,得到 15+15+15=4515+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 解释

\hspace{15pt}初始时,数组为 {0,0,0,0,0,0}\{0, 0, 0, 0, 0, 0\}。

∙ \hspace{23pt}\bullet\,第一次操作,将区间 [1,6][1, 6] 中所有偶数增加 33,得到 {3,3,3,3,3,3}\{3, 3, 3, 3, 3, 3\};

∙ \hspace{23pt}\bullet\,第二次操作,将区间 [2,5][2, 5] 中所有奇数减少 44,得到 {3,−1,−1,−1,−1,3}\{3, -1, -1, -1, -1, 3\};

∙ \hspace{23pt}\bullet\,第三次操作,查询区间 [1,6][1, 6] 的元素和,得到 3−1−1−1−1+3=23-1-1-1-1+3=2;

∙ \hspace{23pt}\bullet\,第四次操作,将区间 [3,6][3, 6] 中所有奇数增加 11,得到 {3,−1,0,0,0,4}\{3, -1, 0, 0, 0, 4\}。注意,原本为奇数的元素在增加 11 后变成了偶数;

∙ \hspace{23pt}\bullet\,第五次操作,查询区间 [2,6][2, 6] 的元素和,得到 −1+0+0+0+4=3-1+0+0+0+4=3;

∙ \hspace{23pt}\bullet\,第六次操作,将区间 [1,4][1, 4] 中所有偶数减少 22,得到 {3,−1,−2,−2,0,4}\{3, -1, -2, -2, 0, 4\};

∙ \hspace{23pt}\bullet\,第七次操作,查询区间 [1,4][1, 4] 的元素和,得到 3−1−2−2=−23-1-2-2=-2。