#P3323. [Scoi2013]多项式的运算

    ID: 2511 传统题 1000ms 512MiB 尝试: 470 已通过: 111 难度: 7 上传者: 标签>CF2200提高+/省选-FHQ Treap 分裂合并按排名分裂标记复合秦九韶算法

[Scoi2013]多项式的运算

题目描述

某天,mzry1992 一边思考着一个项目问题一边在高速公路上骑着摩托车。一个光头踢了他一脚,摩托车损坏,而他也被送进校医院打吊针。现在该项目的截止日期将近,他不得不请你来帮助他完成这个项目。该项目的目的是维护一个动态的关于 xx 的无穷多项式 $f(x)=a_0\times x^0+a_1\times x^1+a_2\times x^2+\cdots$,这个多项式初始时对于所有 ii 有 ai=0a_i=0。

操作者可以进行四种操作:

  • 将 xlx^l 到 xrx^r 这些项的系数乘上某个定值 vv;
  • 将 xlx^l 到 xrx^r 这些项的系数加上某个定值 vv;
  • 将 xlx^l 到 xrx^r 这些项乘上 xx;
  • 将某个定值 vv 代入多项式 f(x)f(x),并输出代入后多项式的值,之后多项式还原为代入前的状况。

经过观察,项目组发现使用者的操作集中在前三种,第四种操作不会出现超过 1010 次。mzry1992 负责这个项目的核心代码,你能帮他实现么。

输入格式

输入的第一行有一个整数 nn 代表操作的个数。

接下来 nn 行,每行一个操作,格式如下:

  • mul L R v 代表第一种操作;
  • add L R v 代表第二种操作;
  • mulx L R 代表第三种操作;
  • query v 代表第四种操作。

输出格式

对于每个第四种操作,输出对应的答案,结果可能较大,需要模 2013042620130426。

6
add 0 1 7
query 1
mul 0 1 7
query 2
mulx 0 1
query 3
14
147
588

样例说明 1

操作一之后,多项式为 f(x)=7x+7f(x)=7x+7。

操作三之后,多项式为 f(x)=49x+49f(x)=49x+49。

操作五之后,多项式为 f(x)=49x2+49xf(x)=49x^2+49x。

数据规模与约定

对于 30%30\% 的数据,1≤n≤5×1031\leq n\leq 5\times 10^3,0≤l≤r≤5×1030\leq l\leq r\leq 5\times 10^3;

对于另外 20%20\% 的数据,不存在 mulx 操作;

对于 100%100\% 的数据,1≤n≤1051\leq n\leq 10^5,0≤l≤r≤1050\leq l\leq r\leq 10^5,0≤v≤1090\leq v\leq 10^9。

提示

应上传者要求,此系列试题不公开,如有异议,本站将删除之。