luogu#P3328. [SDOI2015] 音质检测

[SDOI2015] 音质检测

题目描述

万老板希望在新的智能音乐播放设备 IPOOD\operatorname{IPOOD} 中,实现对波文件音质性能的评定。离散的波文件被考虑为长度为 NN 的整数序列:A1,A2,,ANA_1,A_2,\cdots,A_N。所谓的音质性能检测,可以评定任何的一个区间范围 [L,R][L,R] ,音质性能取决于下述评分:

$$\sum_{L<i<R}F[A_{i-1}+1]F[A_{i+1}-1] \operatorname{mod}\;(10^9+7) $$

其中 FF 是可归纳定义的数列,满足 F1=1F_1=1F2=2F_2=2Fk+2=Fk+1+aFk+bF_{k+2}=F_{k+1}+aF_{k}+b 对于任何 k>0k>0 成立。

其中 aabb 为正整系数。为了可以为用户提供更好的服务体验,并希望对给定的波文件进行修正优化。这一款设备中,还应该支持对波文件的修改。对于给定的区间范围 [L,R][L,R] ,允许用户将 ALA_LARA_R 同时增加一,或同时减少一。

输入格式

输入的第一行有两个正整数,波文件的总长度 NN ,和总的修改与询问次数 QQ

第二行有两个整数,分别表示系数 aabb

之后若干行,一共给出 NN 个正整数 A1A_1ANA_N ,满足 1Ai2×1091\leq A_i\leq 2\times 10^9

之后 QQ 行,每行是下述三种形式之一:

  • plus  L  R:\text{plus}\;L\;R:将波文件数列中下标在区间 [L,R][L,R] 内的元素每一个都加一。
  • minus  L  R:\text{minus}\;L\;R:将波文件数列中下标在区间 [L,R][L,R] 内的元素每一个都减一。
  • query  L  R:\text{query}\;L\;R:询问区间 [L,R][L,R] 的音质性能评分。修改和询问中,均保证 LRL\leq R ,且保证 AiA_i 严格大于总的修改次数加一(修改操作包括 plus\text{plus}minus\text{minus} 两种)。

输出格式

输出若干行,每一行对应一次询问,输出一个整数。

7 7
1 0
3 4 5 6 7 8 9
query 2 4
query 3 7
plus 3 5
query 2 4
plus 4 7
query 3 7
query 1 7
64 
1766 
104 
7479 
7687

提示

N3×105,Q104,0a,b109N\leq 3\times10^5,Q\leq10^4,0\leq a,b\leq10^9