2023-07-18 20:49:31
思路：
一开始的思路是每次存两个值，因为任意两个斐波那契数列合并之后仍然满足斐波那契的基本性质 \(f[x]=f[x-1]+f[x-2]\)。
但是发现这样子每次修改直接的总和得暴力递推求，复杂度爆炸。
为了解决这个突破口，稍微借鉴了一下题解的斐波那契数列性质。
由斐波那契数列性质：\(f(n+m)=f(n+1)*f(m)+f(n)*f(m-1)\) 。
对于区间 \([l,r]\) 的数，\(x\) 为其中一个位置，则需要在 \(x\) 上加上的为 \(f(x-l+1)\ \ (x<-[l,r])\)。
我们将x和l分离开可得：\(f[x+(1-l)]=f[x+1]*f[1-l]+f[x]*f[-l]\)
我们发现，我们可以通过前缀和的方式求出整个区间中 \(f[x]和f[x+1]\) 的和，而每次修改过程中 \(f[1-l]\) 和 \(f[-l]\) 是不变的，可以直接用懒标记下放。
负数的斐波那契数列可以用倒推的方式求得。
由此解决了总和无法 \(O(1)\) 求得的瓶颈
注：在处理pre[]数组的时候要注意略大于n(比如调成n+3)，因为会访问到r+1,此时可能会爆
Code
typedef long long ll;
const int mod=1e9+9;
#define mid (l+r>>1)
int n,m;
ll tr[1200005],pre[300005],tag1[1200005],tag2[1200005];//tag1:f[1-l],tagf2:f[-l]
unordered_map<int,ll>f;
inline void pushup(int root){
tr[root]=(tr[root<<1]+tr[root<<1|1])%mod;
}
void build(int root,int l,int r){
if(l==r){
tr[root]=read();
return;
}
build(root<<1,l,mid),build(root<<1|1,mid+1,r);
pushup(root);
}
inline void pupudown(int root,int l,int r,int a1,int a2){
tag1[root]=(tag1[root]+a1)%mod;
tag2[root]=(tag2[root]+a2)%mod;
tr[root]=(tr[root]+a1*(((pre[r+1]-pre[l])%mod+mod)%mod)%mod+a2*(((pre[r]-pre[l-1])%mod+mod)%mod)%mod)%mod;
}
inline void pushdown(int root,int l,int r){
if(tag1[root]||tag2[root]){
pupudown(root<<1,l,mid,tag1[root],tag2[root]);
pupudown(root<<1|1,mid+1,r,tag1[root],tag2[root]);
tag1[root]=tag2[root]=0;
}
}
void update(int root,int l,int r,int x,int y){
if(x<=l&&r<=y){
pupudown(root,l,r,f[1-x],f[-x]);
return;
}
pushdown(root,l,r);
if(mid>=x)update(root<<1,l,mid,x,y);
if(mid<y)update(root<<1|1,mid+1,r,x,y);
pushup(root);
}
ll query(int root,int l,int r,int x,int y){
if(x<=l&&r<=y){
return tr[root];
}
ll ans=0;
pushdown(root,l,r);
if(mid>=x)ans=query(root<<1,l,mid,x,y)%mod;
if(mid<y)ans=(ans+query(root<<1|1,mid+1,r,x,y))%mod;
pushup(root);
return ans;
}
int main(){
n=read(),m=read();
build(1,1,n);//f[1]=f[0]+f[-1]->f[-1]=f[1]-f[0]
f[0]=0;
f[1]=pre[1]=1;
for(int i=2;i<=n+3;i++){
f[i]=(f[i-1]+f[i-2])%mod;
pre[i]=(pre[i-1]+f[i])%mod;
}
for(int i=-1;i>=-n-3;--i){
f[i]=((f[i+2]-f[i+1])%mod+mod)%mod;
}
while(m--){
int opt=read(),l=read(),r=read();
if(opt&1){
update(1,1,n,l,r);
}else{
printf("%lld\n",query(1,1,n,l,r));
}
}
}