Dotcpp  >  编程题库  >  信息学奥赛一本通T1551-维护序列
题目 2457:

信息学奥赛一本通T1551-维护序列

时间限制: 1s 内存限制: 128MB 提交: 9 解决: 5

题目描述

原题来自: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 的值。

同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。

输出格式

对每个操作 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 次操作后,数列为 {1,10,15,20,25,6,7};

对第 2 次操作,和为 10+15+20=45,模 43 的结果是 22;

经过第 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

测试数据规模如下表所示:


标签