音质检测
测试数据来自 system/1958
描述
万老板希望在新的智能音乐播放设备IPOOD中,实现对波文件音质性能的评定。
离散的波文件被考虑为长度为N的整数序列:\(A_1,A_2,\cdots,A_N\)。所谓的音质性能检测,可以评定任何的一个区间范围\([L,R]\),其音质性能取决于下述评分:
\( \Big\{ \sum_{L<i<R} F[A_{i-1}+1]F[A_{i+1}-1] \Big\} \mod (10^9+7) \)
其中F是可归纳定义的数列,满足\(F[1]=1\),\(F[2]=2\)且\(F[k+2]=F[k+1]+aF[k]+b\)对于任何\(k\ge 1\)成立。其中a 和b为正整系数。
为了可以为用户提供更好的服务体验,并希望对给定的波文件进行修正优化。这一款设备中,还应该支持对波文件的修改。
对于给定的区间范围\([L,R]\),允许用户将\(A[L]\)至\(A[R]\)同时增加一,或同时减少一。
格式
输入格式
输入的第一行有两个正整数,波文件的总长度\(N\),和总的修改与询问次数\(Q\)。
第二行有两个整数,分别表示系数\(a\)和\(b\)。
之后若干行,一共给出\(N\)个正整数\(A_1\)到\(A_N\),满足\(1 \le A[i] \le 2*10^9\)。
之后\(Q\)行,每行是下述三种形式之一:
\(plus~L~R\):将波文件数列中下标在区间\([L,R]\)内的元素每一个都加一。
\(minus~L~R\):将波文件数列中下标在区间\([L,R]\)内的元素每一个都减一。
\(query~L~R\):询问区间\([L,R]\)的音质性能评分。
修改和询问中,均保证\(L\le R\),且保证\(A[i]\)严格大于总的修改次数加一(修改操作包括plus和minus两种)。
输出格式
输出若干行,每一行对应一次询问,输出一个整数。
样例1
样例输入1
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
样例输出1
64
1766
104
7479
7687
样例2
样例输入2
7 12
123456789 987654321
1111111111 1222222222 1333333333
1444444444 1555555555 1666666666 1777777777
query 2 4
query 3 7
plus 3 5
minus 4 6
plus 5 7
query 2 4
query 1 6
plus 4 7
minus 1 4
query 3 7
query 2 6
query 1 7
样例输出2
528103209
239947280
528103209
229970829
524160263
336413855
113033289
限制
对于15%的数据,\(N\le 8000,Q\le 8000\)。
对于100%的数据,\(N\le 100000,Q\le 100000,0\le a,b\le 10^9\)。
此外:
存在15%的数据,每一次修改的区间都是[1,N]。
还存在30%的数据,a=0,b=1。
来源
SDOI 2015 round2 day1