题目描述
原题来自：AHOI 2009
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。
有长为
n
n 的数列，不妨设为
a_1,a_2,\cdots ,a_n
a1
,a2
,⋯,an
。有如下三种操作形式：
把数列中的一段数全部乘一个值；
把数列中的一段数全部加一个值；
询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模
P
P 的值。
输入
第一行两个整数
n
n 和
P
P；
第二行含有
n
n 个非负整数，从左到右依次为
a_1,a_2,\cdots ,a_n
a1
,a2
,⋯,an
；
第三行有一个整数
M
M，表示操作总数；
从第四行开始每行描述一个操作，输入的操作有以下三种形式：
操作
1
1：1 t g c，表示把所有满足
t\le i\le g
t≤i≤g 的
a_i
ai
改为
a_i\times c
ai
×c；
操作
2
2：2 t g c，表示把所有满足
t\le i\le g
t≤i≤g 的
a_i
ai
改为
a_i+c
ai
+c；
操作
3
3：3 t g，询问所有满足
t\le i\le g
t≤i≤g 的
a_i
ai
的和模
P
P 的值。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
输出
对每个操作
3
3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。
样例输入
7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7
样例输出
2
35
8
提示
样例说明
初始时数列为
\{1,2,3,4,5,6,7\}
{1,2,3,4,5,6,7}；
经过第
1
1 次操作后，数列为
\{1,10,15,20,25,6,7\}
{1,10,15,20,25,6,7}；
对第
2
2 次操作，和为
10+15+20=45
10+15+20=45，模
43
43 的结果是
2
2；
经过第
3
3 次操作后，数列为
\{1,10,24,29,34,15,16\}
{1,10,24,29,34,15,16}；
对第
4
4 次操作，和为
1+10+24=35
1+10+24=35，模
43
43 的结果是
35
35；
对第
5
5 次操作，和为
29+34+15+16=94
29+34+15+16=94，模
43
43 的结果是
8
8。
数据范围与提示
对于全部测试数据，
1\le t\le g\le n,0\le c,a_i\le 10^9,1\le P\le 10^9
1≤t≤g≤n,0≤c,ai
≤109,1≤P≤109。
测试数据规模如下表所示：
数据编号 11 2,32,3 44 55 66 77 88 9,109,10
n=
n=
10
10
10^3
103
10^4
104
6\times 10^4
6×104
7\times 10^4
7×104
8\times 10^4
8×104
9\times 10^4
9×104
10^5
105
M=
M=
10
10
10^3
103
10^4
104
6\times 10^4
6×104
7\times 10^4
7×104
8\times 10^4
8×104
9\times 10^4
9×104
10^5
105
来源/分类
ybttg 线段树