华师一附中OI组

标题: P3278 [SCOI2013]多项式的运算 [打印本页]

作者: admin 时间: 2020-4-30 21:41
标题: P3278 [SCOI2013]多项式的运算
https://www.luogu.com.cn/problem/P3278

题目描述
某天，mzry1992 一边思考着一个项目问题一边在高速公路上骑着摩托车。一个光头踢了他一脚，摩托车损坏，而他也被送进校医院打吊针。现在该项目的截止日期将近，他不得不请你来帮助他完成这个项目。

该项目的目的是维护一个动态的关于x 的无穷多项式，这个多项式初始时对于所有i有ai=0。

f(x)=a0x^0+a1x^1+a2x^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

欢迎光临华师一附中OI组 (http://hsyit.cn/)