P13978 数列分块入门 3
题目描述
给定一个长度为 n 的数列 {a1,a2,…,an}。接下来需要依次执行 n 次操作,操作分为以下两种:
∙加法操作:给定区间 [l,r] 和整数 c,将区间内的每个数都增加 c;
∙询问操作:给定区间 [l,r] 和整数 c,求出区间内严格小于 c 的最大元素;若区间内不存在严格小于 c 的元素,则答案为 −1。这个最大值也称为 c 在区间内的前驱。
对于每个询问操作,输出对应的结果。
输入格式
第一行输入一个整数 n(1≦n≦2×105) 代表数列的长度,同时也是操作次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(-2^{31} \leqq a_i \leqq 2^{31}-1\right)$ 代表数列中的元素。
此后 n 行,第 i 行输入四个整数 $\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)$ 代表第 i 次操作。其中 opti=0 表示对区间 [li,ri] 执行加法操作,加数为 ci;opti=1 表示询问 ci 在区间 [li,ri] 内的前驱。
输出格式
对于每个询问操作,新起一行输出一个整数,代表该次询问的答案。若区间内不存在严格小于 ci 的元素,输出 −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 解释
初始时,数列为 {1,2,2,3}。
∙第一次操作将区间 [1,3] 内的每个数增加 1,数列变为 {2,3,3,3};
∙第二次操作询问 4 在区间 [1,4] 内的前驱,区间内严格小于 4 的元素有 2,3,3,3,其中最大值为 3,因此答案为 3;
∙第三次操作将区间 [1,2] 内的每个数增加 2,数列变为 {4,5,3,3};
∙第四次操作询问 4 在区间 [1,2] 内的前驱,区间内的元素为 4,5,没有严格小于 4 的元素,因此答案为 −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 解释
初始时,数列为 {4,1,7,1,9,2}。
∙第一次操作将区间 [1,4] 内的每个数增加 3,数列变为 {7,4,10,4,9,2};
∙第二次操作询问 10 在区间 [1,6] 内的前驱,区间内严格小于 10 的最大元素为 9,因此答案为 9;
∙第三次操作将区间 [2,5] 内的每个数增加 −2,数列变为 {7,2,8,2,7,2};
∙第四次操作询问 8 在区间 [1,3] 内的前驱,区间内严格小于 8 的最大元素为 7,因此答案为 7;
∙第五次操作询问 3 在区间 [5,6] 内的前驱,区间内严格小于 3 的最大元素为 2,因此答案为 2;
∙第六次操作询问 −5 在区间 [1,6] 内的前驱,区间内没有严格小于 −5 的元素,因此答案为 −1。
提示
本系列的测试数据范围与原题不同。
本题共有两个子任务:
∙子任务 1(40 分):1≦n≦105,−231≦ai,c≦231−1,−231≦ans≦231−1;
∙子任务 2(60 分):1≦n≦2×105,−231≦ai,c≦231−1,−231≦ans≦231−1。
其中 ans 表示每次询问操作的答案。对于所有测试数据,每次操作后的 ai 都满足 −231≦ai≦231−1。