LG#P3368. 【模板】树状数组 2

【模板】树状数组 2

P3368 【模板】树状数组 2

题目描述

\hspace{15pt}给定一个长度为 nn 的整数数列 a1,a2,…,ana_1, a_2, \dots, a_n,你需要依次处理 mm 次操作。操作共有下面两种:

∙ \hspace{23pt}\bullet\,将数列中某一个区间内的每一个数都加上一个给定的整数;

∙ \hspace{23pt}\bullet\,求出数列中某一个数的值。

输入格式

\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 个整数 $a_1, a_2, \dots, a_n \left(-2^{30} \leqq a_i \leqq 2^{30}\right)$ 代表数列的初始值。

\hspace{15pt}此后 mm 行,每行先输入一个整数 op(1≦op≦2)op \left(1 \leqq op \leqq 2\right) 代表操作类型,随后在同一行继续输入:

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

∙ \hspace{23pt}\bullet\,若 op=2op = 2,输入一个整数 x(1≦x≦n)x \left(1 \leqq x \leqq n\right),表示询问第 xx 个数的值。

\hspace{15pt}保证在任意时刻,数列中任意一个数的绝对值都不大于 2302^{30}。

输出格式

\hspace{15pt}对于每次 op=2op = 2 的操作,新起一行输出一个整数,代表第 xx 个数当前的值。

测试样例

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
6
10

样例 1 解释

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

∙ \hspace{23pt}\bullet\,操作 "1 2 4 2"\texttt{"1 2 4 2"}:将区间 [2,4]\left[2, 4\right] 内的每个数加上 22,数列变为 {1,7,6,4,3}\{1, 7, 6, 4, 3\};

∙ \hspace{23pt}\bullet\,操作 "2 3"\texttt{"2 3"}:第 33 个数当前为 66;

∙ \hspace{23pt}\bullet\,操作 "1 1 5 -1"\texttt{"1 1 5 -1"}:将区间 [1,5]\left[1, 5\right] 内的每个数加上 −1-1,数列变为 {0,6,5,3,2}\{0, 6, 5, 3, 2\};

∙ \hspace{23pt}\bullet\,操作 "1 3 5 7"\texttt{"1 3 5 7"}:将区间 [3,5]\left[3, 5\right] 内的每个数加上 77,数列变为 {0,6,12,10,9}\{0, 6, 12, 10, 9\};

∙ \hspace{23pt}\bullet\,操作 "2 4"\texttt{"2 4"}:第 44 个数当前为 1010。

\hspace{15pt}因此依次输出 66 和 1010。

6 7
1 -2 3 0 4 6
1 1 3 5
2 2
1 2 4 -1
2 6
1 3 6 2
2 2
2 6
3
6
2
8

样例 2 解释

\hspace{15pt}数列的初始值为 {1,−2,3,0,4,6}\{1, -2, 3, 0, 4, 6\}。

∙ \hspace{23pt}\bullet\,操作 "1 1 3 5"\texttt{"1 1 3 5"}:将区间 [1,3]\left[1, 3\right] 内的每个数加上 55,数列变为 {6,3,8,0,4,6}\{6, 3, 8, 0, 4, 6\};

∙ \hspace{23pt}\bullet\,操作 "2 2"\texttt{"2 2"}:第 22 个数当前为 33;

∙ \hspace{23pt}\bullet\,操作 "1 2 4 -1"\texttt{"1 2 4 -1"}:将区间 [2,4]\left[2, 4\right] 内的每个数加上 −1-1,数列变为 {6,2,7,−1,4,6}\{6, 2, 7, -1, 4, 6\};

∙ \hspace{23pt}\bullet\,操作 "2 6"\texttt{"2 6"}:第 66 个数当前为 66;

∙ \hspace{23pt}\bullet\,操作 "1 3 6 2"\texttt{"1 3 6 2"}:将区间 [3,6]\left[3, 6\right] 内的每个数加上 22,数列变为 {6,2,9,1,6,8}\{6, 2, 9, 1, 6, 8\};

∙ \hspace{23pt}\bullet\,操作 "2 2"\texttt{"2 2"}:第 22 个数当前为 22;

∙ \hspace{23pt}\bullet\,操作 "2 6"\texttt{"2 6"}:第 66 个数当前为 88。

\hspace{15pt}因此依次输出 3,6,2,83, 6, 2, 8。

提示

\hspace{15pt}本题的数据分为以下三档:

∙ \hspace{23pt}\bullet\,对于 30%30\% 的数据,1≦n≦81 \leqq n \leqq 8,1≦m≦101 \leqq m \leqq 10;

∙ \hspace{23pt}\bullet\,对于 70%70\% 的数据,1≦n,m≦1041 \leqq n, m \leqq 10^4;

∙ \hspace{23pt}\bullet\,对于 100%100\% 的数据,1≦n,m≦5×1051 \leqq n, m \leqq 5 \times 10^5。