LG#P13976. 数列分块入门 1

数列分块入门 1

P13976 数列分块入门 1

题目描述

\hspace{15pt}给出一个长度为 nn 的数列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},以及 nn 次操作。每次操作是区间加法或单点查值中的一种。

\hspace{15pt}第 ii 次操作给定四个整数 opt,l,r,c\mathrm{opt}, l, r, c:

∙ \hspace{23pt}\bullet\,若 opt=0\mathrm{opt}=0,表示将区间 [l,r][l,r] 内的每个数都加上 cc;

∙ \hspace{23pt}\bullet\,若 opt=1\mathrm{opt}=1,表示询问当前 ara_r 的值,此时 ll 与 cc 忽略不计。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦3×105)n \left(1 \leqq n \leqq 3 \times 10^5\right) 代表数列长度,同时代表操作次数。

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

\hspace{15pt}此后 nn 行,第 ii 行输入四个整数 $\mathrm{opt}, l, r, c \left(\mathrm{opt} \in \{0,1\}\right)$ 描述第 ii 次操作:

∙ \hspace{23pt}\bullet\,若 opt=0\mathrm{opt}=0,保证 1≦l≦r≦n1 \leqq l \leqq r \leqq n,−263≦c≦263−1-2^{63} \leqq c \leqq 2^{63}-1;

∙ \hspace{23pt}\bullet\,若 opt=1\mathrm{opt}=1,ll 与 cc 忽略不计,可以是任意整数,只要求 1≦r≦n1 \leqq r \leqq n。

\hspace{15pt}保证每次操作结束后,数列中的每个数都满足 −263≦ai≦263−1-2^{63} \leqq a_i \leqq 2^{63}-1。

输出格式

\hspace{15pt}按操作顺序,对于每次 opt=1\mathrm{opt}=1 的操作,新起一行输出一个整数,代表执行该操作时 ara_r 的值。

测试样例

4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0
2
5

样例 1 解释

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

∙ \hspace{23pt}\bullet\,第 11 次操作 opt=0\mathrm{opt}=0,将 [1,3][1,3] 内的数都加 11,数列变为 {2,3,3,3}\{2,3,3,3\};

∙ \hspace{23pt}\bullet\,第 22 次操作 opt=1\mathrm{opt}=1,询问 a1a_1,此时 a1=2a_1=2;

∙ \hspace{23pt}\bullet\,第 33 次操作 opt=0\mathrm{opt}=0,将 [1,2][1,2] 内的数都加 22,数列变为 {4,5,3,3}\{4,5,3,3\};

∙ \hspace{23pt}\bullet\,第 44 次操作 opt=1\mathrm{opt}=1,询问 a2a_2,此时 a2=5a_2=5。

\hspace{15pt}因此依次输出 22 和 55。

6
5 -3 8 0 -6 2
0 2 4 3
1 0 3 0
0 1 6 -2
0 3 3 10
1 0 4 0
1 0 6 0
11
1
0

提示

\hspace{15pt}洛谷的数列分块入门系列的测试数据范围与原题不同。

\hspace{15pt}本题设有子任务:

∙ \hspace{23pt}\bullet\,子任务 11(4040 分):1≦n≦5×1041 \leqq n \leqq 5 \times 10^4;

∙ \hspace{23pt}\bullet\,子任务 22(6060 分):1≦n≦3×1051 \leqq n \leqq 3 \times 10^5。

\hspace{15pt}对于所有数据,1≦n≦3×1051 \leqq n \leqq 3 \times 10^5,−263≦ai,ans≦263−1-2^{63} \leqq a_i, \mathrm{ans} \leqq 2^{63}-1,其中 ans\mathrm{ans} 表示某次询问的答案。保证每次操作后的 aia_i 均满足 −263≦ai≦263−1-2^{63} \leqq a_i \leqq 2^{63}-1。