#8769. 「一本通 4.3 练习 3」维护序列
「一本通 4.3 练习 3」维护序列
题目描述
原题来自:AHOI 2009
老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。
有长为 的数列,不妨设为 。有如下三种操作形式:
- 把数列中的一段数全部乘一个值;
- 把数列中的一段数全部加一个值;
- 询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模 的值。
输入格式
第一行两个整数 和 ;
第二行含有 个非负整数,从左到右依次为 ;
第三行有一个整数 ,表示操作总数;
从第四行开始每行描述一个操作,输入的操作有以下三种形式:
- 操作 :
1 t g c
,表示把所有满足 的 改为 ; - 操作 :
2 t g c
,表示把所有满足 的 改为 ; - 操作 :
3 t g
,询问所有满足 的 的和模 的值。
同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。
输出格式
对每个操作 ,按照它在输入中出现的顺序,依次输出一行一个整数表示询问结果。
样例
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\le t\le g\le n,0\le c,a_i\le 10^9,1\le P\le 10^9+7$。
测试数据规模如下表所示:
数据编号 | ||||||||
---|---|---|---|---|---|---|---|---|