P3278 [SCOI2013]多项式的运算

    • 143通过
    • 414提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 Splay 枚举,暴力 线段树 2013 四川 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 64MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    某天,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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。