TouchStone
  Please Login
Login Sign Up
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3227
  • Problem
  • P3227杨过的黯然销魂掌·树状数组模板
    Limits : Time Limit : 9000 MS   Memory Limit : 262144 KB
    Judgment Tips : 3s,256MB,6组
    Description

    杨过练了黯然销魂掌,一巴掌把序列$a_1,a_2,\dots,a_n$中的连续一段数值打肿了,也就是$a_l,\dots,a_r$每个数增加$x$。打肿了之后需要很多药才能消肿,将$a_l,\dots,a_r$全部消肿需要$a_l+\dots+a_r$那么多药。(杨过很穷没钱买药,只能留个念想,实际毫无效果)。

    Input Format

    第一行两个正整数$n,q$,表示脸的大小和操作的次数。 第二行$n$个数$a_1,a_2,\dots,a_n$,表示脸初始肿胀程度。 从第三行起的连续$q$行,有以下两种操作:

    • $\texttt{1 l r x: }$杨过打了一巴掌
    • $\texttt{2 l r: }$杨过想买药(但没去买)
    Output Format

    对每次$\texttt{2 l r}$的操作输出结果。

    Sample Input

    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

    Sample Output

    15
    34
    32
    33
    50

    Hint

    $1\leq n,q\leq 10^6, 1\leq l\leq r\leq n, |x|\leq10^6, |a_i|\leq10^6$