Home => ProblemSet => 3.9-16:线段树 2
1777: 3.9-16:线段树 2
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 0 Solved: 8[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
如题，已知一个数列，你需要进行下面三种操作：
-
将某区间每一个数乘上 x
-
将某区间每一个数加上 x
-
求出某区间每一个数的和
Input
第一行包含三个整数 n,m,p，分别表示该数列数字的个数、操作的总个数和模数。
第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含若干个整数，表示一个操作，具体如下：
操作 1： 格式：1 x y k 含义：将区间 [x,y] 内每个数乘上 k
操作 2： 格式：2 x y k 含义：将区间 [x,y] 内每个数加上 k
操作 3： 格式：3 x y 含义：输出区间 [x,y] 内每个数的和对 p 取模所得的结果
第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含若干个整数，表示一个操作，具体如下：
操作 1： 格式：1 x y k 含义：将区间 [x,y] 内每个数乘上 k
操作 2： 格式：2 x y k 含义：将区间 [x,y] 内每个数加上 k
操作 3： 格式：3 x y 含义：输出区间 [x,y] 内每个数的和对 p 取模所得的结果
Output
输出包含若干行整数，即为所有操作 3 的结果。
Sample Input Copy
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4
Sample Output Copy
17
2
HINT
样例解释：
故输出应为 17、2（ 40 mod 38 = 2 ）
对于 30% 的数据：n≤8，m≤10
对于 70% 的数据：n≤103，m≤104
对于 100% 的数据：n≤105，m≤105
除样例外，p=571373
故输出应为 17、2（ 40 mod 38 = 2 ）
对于 30% 的数据：n≤8，m≤10
对于 70% 的数据：n≤103，m≤104
对于 100% 的数据：n≤105，m≤105
除样例外，p=571373