LG#P13978. 数列分块入门 3

数列分块入门 3

P13978 数列分块入门 3

题目描述

\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,求出区间内严格小于 cc 的最大元素;若区间内不存在严格小于 cc 的元素,则答案为 −1-1。这个最大值也称为 cc 在区间内的前驱。

\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 表示询问 cic_i 在区间 [li,ri][l_i, r_i] 内的前驱。

输出格式

\hspace{15pt}对于每个询问操作,新起一行输出一个整数,代表该次询问的答案。若区间内不存在严格小于 cic_i 的元素,输出 −1-1。

测试样例

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

样例 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\,第二次操作询问 44 在区间 [1,4][1, 4] 内的前驱,区间内严格小于 44 的元素有 2,3,3,32, 3, 3, 3,其中最大值为 33,因此答案为 33;

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

∙ \hspace{23pt}\bullet\,第四次操作询问 44 在区间 [1,2][1, 2] 内的前驱,区间内的元素为 4,54, 5,没有严格小于 44 的元素,因此答案为 −1-1。

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

样例 2 解释

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

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

∙ \hspace{23pt}\bullet\,第二次操作询问 1010 在区间 [1,6][1, 6] 内的前驱,区间内严格小于 1010 的最大元素为 99,因此答案为 99;

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

∙ \hspace{23pt}\bullet\,第四次操作询问 88 在区间 [1,3][1, 3] 内的前驱,区间内严格小于 88 的最大元素为 77,因此答案为 77;

∙ \hspace{23pt}\bullet\,第五次操作询问 33 在区间 [5,6][5, 6] 内的前驱,区间内严格小于 33 的最大元素为 22,因此答案为 22;

∙ \hspace{23pt}\bullet\,第六次操作询问 −5-5 在区间 [1,6][1, 6] 内的前驱,区间内没有严格小于 −5-5 的元素,因此答案为 −1-1。

提示

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

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

∙ \hspace{23pt}\bullet\,子任务 1(40 分):1≦n≦1051 \leqq n \leqq 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{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。