P13976 数列分块入门 1
题目描述
给出一个长度为 n 的数列 {a1,a2,…,an},以及 n 次操作。每次操作是区间加法或单点查值中的一种。
第 i 次操作给定四个整数 opt,l,r,c:
∙若 opt=0,表示将区间 [l,r] 内的每个数都加上 c;
∙若 opt=1,表示询问当前 ar 的值,此时 l 与 c 忽略不计。
输入格式
第一行输入一个整数 n(1≦n≦3×105) 代表数列长度,同时代表操作次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(-2^{63} \leqq a_i \leqq 2^{63}-1\right)$ 代表数列的初始值。
此后 n 行,第 i 行输入四个整数 $\mathrm{opt}, l, r, c \left(\mathrm{opt} \in \{0,1\}\right)$ 描述第 i 次操作:
∙若 opt=0,保证 1≦l≦r≦n,−263≦c≦263−1;
∙若 opt=1,l 与 c 忽略不计,可以是任意整数,只要求 1≦r≦n。
保证每次操作结束后,数列中的每个数都满足 −263≦ai≦263−1。
输出格式
按操作顺序,对于每次 opt=1 的操作,新起一行输出一个整数,代表执行该操作时 ar 的值。
测试样例
4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0
2
5
样例 1 解释
初始数列为 {1,2,2,3}。
∙第 1 次操作 opt=0,将 [1,3] 内的数都加 1,数列变为 {2,3,3,3};
∙第 2 次操作 opt=1,询问 a1,此时 a1=2;
∙第 3 次操作 opt=0,将 [1,2] 内的数都加 2,数列变为 {4,5,3,3};
∙第 4 次操作 opt=1,询问 a2,此时 a2=5。
因此依次输出 2 和 5。
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
提示
洛谷的数列分块入门系列的测试数据范围与原题不同。
本题设有子任务:
∙子任务 1(40 分):1≦n≦5×104;
∙子任务 2(60 分):1≦n≦3×105。
对于所有数据,1≦n≦3×105,−263≦ai,ans≦263−1,其中 ans 表示某次询问的答案。保证每次操作后的 ai 均满足 −263≦ai≦263−1。