P3227杨过的黯然销魂掌·树状数组模板 | ||
|
问题描述
杨过练了黯然销魂掌,一巴掌把序列$a_1,a_2,\dots,a_n$中的连续一段数值打肿了,也就是$a_l,\dots,a_r$每个数增加$x$。打肿了之后需要很多药才能消肿,将$a_l,\dots,a_r$全部消肿需要$a_l+\dots+a_r$那么多药。(杨过很穷没钱买药,只能留个念想,实际毫无效果)。
输入格式
第一行两个正整数$n,q$,表示脸的大小和操作的次数。 第二行$n$个数$a_1,a_2,\dots,a_n$,表示脸初始肿胀程度。 从第三行起的连续$q$行,有以下两种操作:
- $\texttt{1 l r x: }$杨过打了一巴掌
- $\texttt{2 l r: }$杨过想买药(但没去买)
输出格式
对每次$\texttt{2 l r}$的操作输出结果。
样例输入
5 10
2 6 6 1 1
2 1 4
1 2 5 10
2 1 3
2 2 3
1 2 2 8
1 2 3 7
1 4 4 10
2 1 2
1 4 5 6
2 3 4
样例输出
15
34
32
33
50
提示
$1\leq n,q\leq 10^6, 1\leq l\leq r\leq n, |x|\leq10^6, |a_i|\leq10^6$