华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1146|回复: 0
打印 上一主题 下一主题

P3278 [SCOI2013]多项式的运算

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2020-4-30 21:41:58 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
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
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-25 15:02 , Processed in 0.101643 second(s), 25 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表