LG#P3372. 【模板】线段树 1

【模板】线段树 1

P3372 【模板】线段树 1

题目描述

\hspace{15pt}给定一个长度为 nn 的数列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},你需要支持下面两种操作:

∙ \hspace{23pt}\bullet\,将某个区间内的每一个数都加上 kk;

∙ \hspace{23pt}\bullet\,求出某个区间内每一个数的和。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦105)n, m \left(1 \leqq n, m \leqq 10^5\right) 代表数列中的元素数量和操作总次数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 2 \times 10^{18}\right)$ 代表数列的初始值。

\hspace{15pt}此后 mm 行,第 ii 行先输入一个整数 op(1≦op≦2)op \left(1 \leqq op \leqq 2\right) 代表第 ii 次操作的类型:

∙ \hspace{23pt}\bullet\,若 op=1op=1,再输入三个整数 $x, y, k \left(1 \leqq x \leqq y \leqq n;\ 1 \leqq k \leqq 2 \times 10^{18}\right)$,表示将区间 [x,y][x,y] 内的每个数加上 kk;

∙ \hspace{23pt}\bullet\,若 op=2op=2,再输入两个整数 x,y(1≦x≦y≦n)x, y \left(1 \leqq x \leqq y \leqq n\right),表示询问区间 [x,y][x,y] 内每个数的和。

\hspace{15pt}保证任意时刻数列中所有数的和不超过 2×10182 \times 10^{18}。

输出格式

\hspace{15pt}按操作顺序,对于每次 op=2op=2 的操作,新起一行输出一个整数,代表该次询问的答案。

测试样例

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
11
8
20

样例 1 解释

\hspace{15pt}初始数列为 {1,5,4,2,3}\{1,5,4,2,3\}。

∙ \hspace{23pt}\bullet\,第 11 次操作询问 [2,4][2,4] 的和,为 5+4+2=115+4+2=11;

∙ \hspace{23pt}\bullet\,第 22 次操作将 [2,3][2,3] 内的数都加 22,数列变为 {1,7,6,2,3}\{1,7,6,2,3\};

∙ \hspace{23pt}\bullet\,第 33 次操作询问 [3,4][3,4] 的和,为 6+2=86+2=8;

∙ \hspace{23pt}\bullet\,第 44 次操作将 [1,5][1,5] 内的数都加 11,数列变为 {2,8,7,3,4}\{2,8,7,3,4\};

∙ \hspace{23pt}\bullet\,第 55 次操作询问 [1,4][1,4] 的和,为 2+8+7+3=202+8+7+3=20。

\hspace{15pt}因此依次输出 11,8,2011,8,20。

6 6
4 7 1 9 3 5
2 1 6
1 2 5 4
2 2 5
1 1 3 6
2 1 3
2 4 6
29
36
38
25

提示

\hspace{15pt}对于 15%15\% 的数据,n≦8n \leqq 8,m≦10m \leqq 10;

\hspace{15pt}对于 35%35\% 的数据,n≦103n \leqq 10^3,m≦104m \leqq 10^4;

\hspace{15pt}对于 100%100\% 的数据,1≦n,m≦1051 \leqq n, m \leqq 10^5,ai,ka_i, k 均为正数,且任意时刻数列中所有数的和不超过 2×10182 \times 10^{18}。