LG#P13977. 数列分块入门 2

数列分块入门 2

P13977 数列分块入门 2

题目描述

\hspace{15pt}给定一个长度为 nn 的数列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\}。接下来需要依次执行 nn 次操作,操作分为以下两种:

∙ \hspace{23pt}\bullet\,加法操作:给定区间 [l,r][l, r] 和整数 cc,将区间内的每个数都增加 cc;

∙ \hspace{23pt}\bullet\,询问操作:给定区间 [l,r][l, r] 和整数 cc,令 x=c2x = c^2,求出区间内严格小于 xx 的元素个数。

\hspace{15pt}对于每个询问操作,输出对应的结果。

输入格式

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

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

\hspace{15pt}此后 nn 行,第 ii 行输入四个整数 $\mathrm{opt}_i, l_i, r_i, c_i \left(\mathrm{opt}_i \in \{0, 1\};\ 1 \leqq l_i \leqq r_i \leqq n;\ -2^{31} \leqq c_i \leqq 2^{31}-1\right)$ 代表第 ii 次操作。其中 opti=0\mathrm{opt}_i = 0 表示对区间 [li,ri][l_i, r_i] 执行加法操作,加数为 cic_i;opti=1\mathrm{opt}_i = 1 表示对区间 [li,ri][l_i, r_i] 执行询问操作,此时 x=ci2x = c_i^2。

输出格式

\hspace{15pt}对于每个询问操作,新起一行输出一个整数,代表该次询问的答案。答案不超过 231−12^{31}-1。

测试样例

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

样例 1 解释

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

∙ \hspace{23pt}\bullet\,第一次操作将区间 [1,3][1, 3] 内的每个数增加 11,数列变为 {2,3,3,3}\{2, 3, 3, 3\};

∙ \hspace{23pt}\bullet\,第二次操作询问区间 [1,3][1, 3],此时 x=22=4x = 2^2 = 4,区间内 2,3,32, 3, 3 都严格小于 44,因此答案为 33;

∙ \hspace{23pt}\bullet\,第三次操作询问区间 [1,4][1, 4],此时 x=12=1x = 1^2 = 1,区间内没有严格小于 11 的元素,因此答案为 00;

∙ \hspace{23pt}\bullet\,第四次操作询问区间 [2,3][2, 3],此时 x=22=4x = 2^2 = 4,区间内 3,33, 3 都严格小于 44,因此答案为 22。

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

样例 2 解释

\hspace{15pt}初始时,数列为 {5,−3,8,0,2,−7}\{5, -3, 8, 0, 2, -7\}。

∙ \hspace{23pt}\bullet\,第一次操作询问区间 [1,6][1, 6],此时 x=32=9x = 3^2 = 9,全体元素都严格小于 99,因此答案为 66;

∙ \hspace{23pt}\bullet\,第二次操作将区间 [2,4][2, 4] 内的每个数增加 1010,数列变为 {5,7,18,10,2,−7}\{5, 7, 18, 10, 2, -7\};

∙ \hspace{23pt}\bullet\,第三次操作询问区间 [1,4][1, 4],此时 x=42=16x = 4^2 = 16,区间内 5,7,105, 7, 10 严格小于 1616,因此答案为 33;

∙ \hspace{23pt}\bullet\,第四次操作询问区间 [2,4][2, 4],此时 x=02=0x = 0^2 = 0,区间内没有严格小于 00 的元素,因此答案为 00;

∙ \hspace{23pt}\bullet\,第五次操作将区间 [1,6][1, 6] 内的每个数增加 −3-3,数列变为 {2,4,15,7,−1,−10}\{2, 4, 15, 7, -1, -10\};

∙ \hspace{23pt}\bullet\,第六次操作询问区间 [1,6][1, 6],此时 x=42=16x = 4^2 = 16,全体元素都严格小于 1616,因此答案为 66。

提示

\hspace{15pt}本系列的测试数据范围与原题不同。

\hspace{15pt}本题共有两个子任务:

∙ \hspace{23pt}\bullet\,子任务 1(40 分):1≦n≦5×1041 \leqq n \leqq 5 \times 10^4,−231≦ai,c≦231−1-2^{31} \leqq a_i, c \leqq 2^{31}-1,−231≦ans≦231−1-2^{31} \leqq \mathrm{ans} \leqq 2^{31}-1;

∙ \hspace{23pt}\bullet\,子任务 2(60 分):1≦n≦2×1051 \leqq n \leqq 2 \times 10^5,−231≦ai,c≦231−1-2^{31} \leqq a_i, c \leqq 2^{31}-1,−231≦ans≦231−1-2^{31} \leqq \mathrm{ans} \leqq 2^{31}-1。

\hspace{15pt}其中 ans\mathrm{ans} 表示每次询问操作的答案。对于所有测试数据,不保证每次操作后的 aia_i 都满足 −231≦ai≦231−1-2^{31} \leqq a_i \leqq 2^{31}-1。