1864: 维护序列
题目描述
原题来自:AHOI 2009
老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。 有长为 n 的数列,不妨设为 a1,a2,⋯,an 。有如下三种操作形式: 把数列中的一段数全部乘一个值; 把数列中的一段数全部加一个值; 询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模 P 的值。
输入
第一行两个整数 n 和 P ;
第二行含有 n 个非负整数,从左到右依次为 a1,a2,⋯,an ;
第三行有一个整数 M ,表示操作总数;
从第四行开始每行描述一个操作,输入的操作有以下三种形式:
操作 1:1 t g c ,表示把所有满足 t≤i≤g 的 ai 改为 ai×c ;
操作 2:2 t g c ,表示把所有满足 t≤i≤g 的 ai 改为 ai+c ;
操作 3:3 t g ,询问所有满足 t≤i≤g 的 ai 的和模 P 的值。 同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。
输出
样例输入 复制
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 次操作后,数列为 {1,10,15,20,25,6,7} ;
对第 2 次操作,和为 10+15+20=45 ,模 43 的结果是 2;
经过第 3 次操作后,数列为 {1,10,24,29,34,15,16} ;
对第 4 次操作,和为 1+10+24=35 ,模 43 的结果是 35 ;
对第 5 次操作,和为 29+34+15+16=94 ,模 43 的结果是 8 。
数据范围与提示: 对于全部测试数据,1≤t≤g≤n,0≤c,ai≤109,1≤P≤109 。
测试数据规模如下表所: