DJL为了避免成为一只咸鱼，来找czgj学习Fibonacci数列。
通过czgj的谆谆教导，DJL明白了Fibonacci数列是这样定义的：
F(1)=1;F(2)=1;F(n)=F(n-1)+F(n-2)(n>2)
Czgj深谙熟能生巧的道理，于是他给了DJL一个数列，并安排了如下的训练计划：
1、“1 L r”，表示给ai 加上F(i-L+1) ，其中L<=i<=r ；
2、“2 L r”，表示询问 的值。
DJL经过长时间的学习，感觉身体被掏空，他希望你能帮他解决这个问题。
暴力每一次操作都要O(n)，我們考慮一下怎麼可以讓修改複雜度降低為O(1)
我們可以維護一個差分數組d，這個數組可以維護增量
每次修改操作可以將d[l]+1,d[r+1]-f[l-r+2],d[r+2]-f[l-r+1]
然後做一遍前綴和,d[i]=d[i-1]+d[i-2]，一直做到d[r+2]為止
所以,d[l]+=1,d[l+1]+=1,d[l+r]+=2……d[r+1]+=f[l-r+1]+f[l-r]-f[l-r+2]==0 d[r+2]+=f[l-r+1]-f[l-r+1]==0
我們可以繼續將原數組和d數組做一遍前綴和，累加一遍，再做一下前綴和就是答案
但是，做完修改以後再做一遍查詢，需要每次重算一遍數組。還是很慢
可以考慮維護一個修改棧f，記錄需要處理的修改操作
可以每k次操作以後重算一遍d數組
在重算d數組時，按照上面的規則計算d數組
最終，求一遍前綴和，將f數組清空，這樣我們就得到了增量數組d
增量數組d可以與a相加，得到增量和，然後這個前綴和就是處理完f數組前的詢問的情況
對於後面的詢問，我們可以暴力算出f數組的詢問對其的影響，最後在計算d數組的增量和即可
這樣，我們需要O(k*m)的時間計算數組，也要重算數組m/k次，需要O(m/k*n)
總時間複雜度為O(k*m+m*n/k)
事實證明，當k=400時速度較快
#include<bits/stdc++.h>
#define mo 1000000009
using namespace std;
typedef long long ll;
struct no{
ll l,r;
}f[100010];
ll ct,n,m,a[100010],f1[100010],f2[100010],d[100010],s[100010];
int main(){
scanf("%lld%lld",&n,&m);
f1[1]=1;f2[1]=1;
for(ll i=2;i<=n;i++){
f1[i]=(f1[i-1]+f1[i-2])%mo;
f2[i]=(f2[i-1]+f1[i])%mo;
}
for(ll i=1;i<=n;i++){
scanf("%lld",&a[i]);
s[i]=(s[i-1]+a[i])%mo;
}
for(ll j=1;j<=m;j++){
ll op,l,r;
scanf("%lld%lld%lld",&op,&l,&r);
if(op==1)f[++ct]=(no){l,r};
if(op==2){
ll v=0;
for(ll i=1;i<=ct;i++){
if(r<f[i].l||f[i].r<l)continue;
v=(v-f2[max(l,f[i].l)-f[i].l]+f2[min(r,f[i].r)-f[i].l+1]+mo)%mo;
}
printf("%lld\n",(v+s[r]-s[l-1]+mo)%mo);
}
if(ct==400){
memset(d,0,sizeof(d));
for(ll i=1;i<=ct;i++){
int a=f[i].l,b=f[i].r;
d[a]=(d[a]+1)%mo;
d[b+1]=(d[b+1]-f1[b-a+2]+mo)%mo;
d[b+2]=(d[b+2]-f1[b-a+1]+mo)%mo;
}
for(ll i=1;i<=n;i++)
d[i]=(d[i]+d[i-1]+d[i-2])%mo;
for(ll i=1;i<=n;i++){
a[i]=(a[i]+d[i])%mo;
s[i]=(s[i-1]+a[i])%mo;
}
ct=0;
}
}
}