维护数列
题目描述
给定长度为 N 的非负整数序列 a1,…,aN,需要支持:
- 区间所有数乘以一个值。
- 区间所有数加上一个值。
- 查询区间所有数之和对 P 取模的结果。
输入格式
从标准输入读入。第一行两个正整数 N,P。
第二行 N 个非负整数 a1,…,aN。
第三行一个整数 M,表示操作数。接下来 M 行,每行为以下格式之一:
1 t g c:把所有 t≤i≤g 的 ai 乘以 c。
2 t g c:把所有 t≤i≤g 的 ai 加上 c。
3 t g:查询 ∑i=tgai 对 P 取模的结果。
输出格式
每个类型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,10,15,20,25,6,7),第二次操作查询得到 45mod43=2。
第三次操作后为 (1,10,24,29,34,15,16)。最后两次查询分别为 35mod43=35 和 94mod43=8。
数据范围
1≤N,M≤105,1≤P,c≤2×109,0≤ai≤2×109,1≤t≤g≤N。