LG#P13982. 数列分块入门 7

数列分块入门 7

P13982 数列分块入门 7

题目描述

\hspace{15pt}给出一个长度为 nn 的数列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},以及 nn 次操作。每次操作是区间加法、区间乘法或单点询问中的一种。

\hspace{15pt}第 ii 次操作给定四个整数 opt,l,r,c\mathrm{opt}, l, r, c:

∙ \hspace{23pt}\bullet\,若 opt=0\mathrm{opt}=0,表示将区间 [l,r][l,r] 内的每个数都加上 cc;

∙ \hspace{23pt}\bullet\,若 opt=1\mathrm{opt}=1,表示将区间 [l,r][l,r] 内的每个数都乘上 cc;

∙ \hspace{23pt}\bullet\,若 opt=2\mathrm{opt}=2,表示询问当前 ara_r 对 1000710007 取模的值,此时 ll 与 cc 忽略不计。你需要输出非负的余数。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦3×105)n \left(1 \leqq n \leqq 3 \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}, l, r, c \left(\mathrm{opt} \in \{0,1,2\}\right)$ 描述第 ii 次操作:

∙ \hspace{23pt}\bullet\,若 opt=0\mathrm{opt}=0 或 opt=1\mathrm{opt}=1,保证 1≦l≦r≦n1 \leqq l \leqq r \leqq n,−231≦c≦231−1-2^{31} \leqq c \leqq 2^{31}-1;

∙ \hspace{23pt}\bullet\,若 opt=2\mathrm{opt}=2,ll 与 cc 忽略不计,可以是任意整数,只要求 1≦r≦n1 \leqq r \leqq n。

输出格式

\hspace{15pt}按操作顺序,对于每次 opt=2\mathrm{opt}=2 的操作,新起一行输出一个整数,代表执行该操作时 ara_r 对 1000710007 取模的非负余数。

测试样例

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 解释

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

∙ \hspace{23pt}\bullet\,第 11 次操作 opt=0\mathrm{opt}=0,将 [1,3][1,3] 内的数都加 11,数列变为 {2,3,3,3,9,3,2}\{2,3,3,3,9,3,2\};

∙ \hspace{23pt}\bullet\,第 22 次操作 opt=2\mathrm{opt}=2,询问 a3a_3,3 mod 10007=33 \bmod 10007=3;

∙ \hspace{23pt}\bullet\,第 33 次操作 opt=1\mathrm{opt}=1,将 [1,4][1,4] 内的数都乘 44,数列变为 {8,12,12,12,9,3,2}\{8,12,12,12,9,3,2\};

∙ \hspace{23pt}\bullet\,第 44 次操作 opt=0\mathrm{opt}=0,将 [1,7][1,7] 内的数都加 22,数列变为 {10,14,14,14,11,5,4}\{10,14,14,14,11,5,4\};

∙ \hspace{23pt}\bullet\,第 55 次操作 opt=1\mathrm{opt}=1,将 [2,6][2,6] 内的数都乘 44,数列变为 {10,56,56,56,44,20,4}\{10,56,56,56,44,20,4\};

∙ \hspace{23pt}\bullet\,第 66 次操作 opt=1\mathrm{opt}=1,将 [1,6][1,6] 内的数都乘 55,数列变为 {50,280,280,280,220,100,4}\{50,280,280,280,220,100,4\};

∙ \hspace{23pt}\bullet\,第 77 次操作 opt=2\mathrm{opt}=2,询问 a6a_6,100 mod 10007=100100 \bmod 10007=100。

\hspace{15pt}因此依次输出 33 和 100100。

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

提示

\hspace{15pt}洛谷的数列分块入门系列的测试数据范围与原题不同。

\hspace{15pt}本题设有子任务:

∙ \hspace{23pt}\bullet\,子任务 11(4040 分):1≦n≦1051 \leqq n \leqq 10^5;

∙ \hspace{23pt}\bullet\,子任务 22(6060 分):1≦n≦3×1051 \leqq n \leqq 3 \times 10^5。

\hspace{15pt}对于所有数据,1≦n≦3×1051 \leqq n \leqq 3 \times 10^5,−231≦ai≦231−1-2^{31} \leqq a_i \leqq 2^{31}-1,opt∈{0,1,2}\mathrm{opt} \in \{0,1,2\};当 opt∈{0,1}\mathrm{opt} \in \{0,1\} 时 1≦l≦r≦n1 \leqq l \leqq r \leqq n,当 opt=2\mathrm{opt}=2 时 1≦r≦n1 \leqq r \leqq n。