P13982 数列分块入门 7
题目描述
给出一个长度为 n 的数列 {a1,a2,…,an},以及 n 次操作。每次操作是区间加法、区间乘法或单点询问中的一种。
第 i 次操作给定四个整数 opt,l,r,c:
∙若 opt=0,表示将区间 [l,r] 内的每个数都加上 c;
∙若 opt=1,表示将区间 [l,r] 内的每个数都乘上 c;
∙若 opt=2,表示询问当前 ar 对 10007 取模的值,此时 l 与 c 忽略不计。你需要输出非负的余数。
输入格式
第一行输入一个整数 n(1≦n≦3×105) 代表数列长度,同时代表操作次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(-2^{31} \leqq a_i \leqq 2^{31}-1\right)$ 代表数列的初始值。
此后 n 行,第 i 行输入四个整数 $\mathrm{opt}, l, r, c \left(\mathrm{opt} \in \{0,1,2\}\right)$ 描述第 i 次操作:
∙若 opt=0 或 opt=1,保证 1≦l≦r≦n,−231≦c≦231−1;
∙若 opt=2,l 与 c 忽略不计,可以是任意整数,只要求 1≦r≦n。
输出格式
按操作顺序,对于每次 opt=2 的操作,新起一行输出一个整数,代表执行该操作时 ar 对 10007 取模的非负余数。
测试样例
7
1 2 2 3 9 3 2
0 1 3 1
2 1 3 1
1 1 4 4
0 1 7 2
1 2 6 4
1 1 6 5
2 2 6 4
3
100
样例 1 解释
初始数列为 {1,2,2,3,9,3,2}。
∙第 1 次操作 opt=0,将 [1,3] 内的数都加 1,数列变为 {2,3,3,3,9,3,2};
∙第 2 次操作 opt=2,询问 a3,3mod10007=3;
∙第 3 次操作 opt=1,将 [1,4] 内的数都乘 4,数列变为 {8,12,12,12,9,3,2};
∙第 4 次操作 opt=0,将 [1,7] 内的数都加 2,数列变为 {10,14,14,14,11,5,4};
∙第 5 次操作 opt=1,将 [2,6] 内的数都乘 4,数列变为 {10,56,56,56,44,20,4};
∙第 6 次操作 opt=1,将 [1,6] 内的数都乘 5,数列变为 {50,280,280,280,220,100,4};
∙第 7 次操作 opt=2,询问 a6,100mod10007=100。
因此依次输出 3 和 100。
6
3 -5 10006 7 0 -1
0 1 4 5
1 2 5 3
2 0 2 0
2 0 3 0
0 4 6 -100
2 0 5 0
0
12
9907
提示
洛谷的数列分块入门系列的测试数据范围与原题不同。
本题设有子任务:
∙子任务 1(40 分):1≦n≦105;
∙子任务 2(60 分):1≦n≦3×105。
对于所有数据,1≦n≦3×105,−231≦ai≦231−1,opt∈{0,1,2};当 opt∈{0,1} 时 1≦l≦r≦n,当 opt=2 时 1≦r≦n。