[SCOI2013] 多项式的运算
题目描述
某天,mzry1992 一边思考着一个项目问题一边在高速公路上骑着摩托车。一个光头踢了他一脚,摩托车损坏,而他也被送进校医院打吊针。现在该项目的截止日期将近,他不得不请你来帮助他完成这个项目。
该项目的目的是维护一个动态的关于x 的无穷多项式 ,这个多项式初始时对于所有i有$a_i = 0$。
$f(x)=a_0x^0+a_1x^1+a_2x^2...$
操作者可以进行四种操作:
将$x^L$ 到$x^R$ 这些项的系数乘上某个定值v
将$x^L$ 到$x^R$ 这些项的系数加上某个定值v
将$x^L 到x^R $这些项乘上x变量
将某个定值v代入多项式F(x),并输出代入后多项式的值,之后多项式还原为代入前的状况
经过观察,项目组发现使用者的操作集中在前三种,第四种操作不会出现超过10次。mzry1992 负责这个项目的核心代码,你能帮他实现么?
输入输出格式
输入格式
输入的第一行有一个整数n 代表操作的个数。
接下来n 行,每行一个操作,格式如下:
mul L R v 代表第一种操作
add L R v 代表第二种操作
mulx L R 代表第三种操作
query v 代表第四种操作
输出格式
对于每个query 操作,输出对应的答案,结果可能较大,需要模上20130426。
输入输出样例
输入样例 #1
6
add 0 1 7
query 1
mul 0 1 7
query 2
mulx 0 1
query 3
输出样例 #1
14
147
588
说明
【样例解释】
操作一之后,多项式为F(x) = 7x + 7。
操作三之后,多项式为F(x) = 49x + 49。
操作五之后,多项式为F(x) = 49x^2 + 49x。
【数据范围与约定】
对于30% 的数据:N ≤ 5000,0 ≤ L ≤ R ≤ 5000,0 ≤ v ≤ 10^9
另有20% 的数据:N ≤ 10^5,0 ≤ L ≤ R ≤ 10^5,0 ≤ v ≤ 10^9,没有mulx 操作
剩下的50% 的数据:N ≤ 10^5,0 ≤ L ≤ R ≤ 10^5,0 ≤v ≤ 10^9