题目链接

Codeforces方向
Luogu方向

题目解法

首先如果多次加斐波那契数可以合并成一个 $tag$ 的话，那么这就是一个普通的线段树题
考虑合并斐波那契数的 $tag$，即每个数的 $tag$ 仅和当前点的位置有关

考虑一个重要的公式： f i b n + m = f i b n + 1 f i b m + f i b n f i b m − 1 fib_{n+m}=fib_{n+1}fib_{m}+fib_{n}fib_{m-1} fibn+m​=fibn+1​fibm​+fibn​fibm−1​
把 a i a_i ai​ 加上的 f i b i − l + 1 fib_{i-l+1} fibi−l+1​ 带入可得
f i b i − l + 1 = f i b − l + 1 ∗ f i b i + 1 + f i b − l ∗ f i b i fib_{i-l+1}=fib_{-l+1}*fib_{i+1}+fib_{-l}*fib_i fibi−l+1​=fib−l+1​∗fibi+1​+fib−l​∗fibi​
其中 f i b − l + 1 fib_{-l+1} fib−l+1​ 与 f i b − l fib_{-l} fib−l​ 都是常数，所以只要打两个 $tag$ 分别记录乘多少个 f i b i + 1 fib_{i+1} fibi+1​ 和 f i b i fib_i fibi​ 即可
对于 f i b − i ( i > 0 ) fib_{-i}(i>0) fib−i​(i>0) 可以逆推，即 f i b − i = f i b − i + 2 − f i b − i + 1 fib_{-i}=fib_{-i+2}-fib_{-i+1} fib−i​=fib−i+2​−fib−i+1​

#include 
using namespace std;
typedef long long LL;
const int N(300100),MOD(1e9+9);
int n,q,a[N],fib[N],rfib[N];
int seg[N<<2],tag0[N<<2],tag1[N<<2];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
void build(int l,int r,int x){if(l==r){ seg[x]=a[l];return;}int mid=(l+r)>>1;build(l,mid,x<<1),build(mid+1,r,x<<1^1);seg[x]=(seg[x<<1]+seg[x<<1^1])%MOD; 
}
void down(int l,int r,int x,int tg0,int tg1){seg[x]=(LL)(seg[x]+(LL)tg0*(fib[r+1]-fib[l]+MOD)%MOD+(LL)tg1*(fib[r]-fib[l-1]+MOD)%MOD)%MOD;(tag0[x]+=tg0)%=MOD,(tag1[x]+=tg1)%=MOD;
}
void pushdown(int l,int r,int mid,int x){down(l,mid,x<<1,tag0[x],tag1[x]),down(mid+1,r,x<<1^1,tag0[x],tag1[x]);tag0[x]=tag1[x]=0;
}
void modify(int l,int r,int x,int L,int R){if(L<=l&&r<=R){
//		cout<seg[x]=(LL)(seg[x]+(LL)rfib[L-1]*(fib[r+1]-fib[l]+MOD)%MOD+(LL)rfib[L]*(fib[r]-fib[l-1]+MOD)%MOD)%MOD;
//		cout<(tag0[x]+=rfib[L-1])%=MOD,(tag1[x]+=rfib[L])%=MOD;return;}int mid=(l+r)>>1;pushdown(l,r,mid,x);if(mid>=L) modify(l,mid,x<<1,L,R);if(mid<R) modify(mid+1,r,x<<1^1,L,R);seg[x]=(seg[x<<1]+seg[x<<1^1])%MOD;
}
int query(int l,int r,int x,int L,int R){if(L<=l&&r<=R) return seg[x];int mid=(l+r)>>1,res=0;pushdown(l,r,mid,x);if(mid>=L) res=(res+query(l,mid,x<<1,L,R))%MOD;if(mid<R) res=(res+query(mid+1,r,x<<1^1,L,R))%MOD;return res;
}
int main(){n=read(),q=read();fib[0]=0,fib[1]=fib[2]=1;for(int i=3;i<=n+1;i++) fib[i]=(fib[i-1]+fib[i-2])%MOD;for(int i=1;i<=n+1;i++) fib[i]=(fib[i]+fib[i-1])%MOD;rfib[0]=0,rfib[1]=1,rfib[2]=MOD-1;for(int i=3;i<=n+1;i++) rfib[i]=(rfib[i-2]-rfib[i-1]+MOD)%MOD;
//	for(int i=1;i<=n+1;i++) cout<
//	cout<<'\n'; for(int i=1;i<=n;i++) a[i]=read();build(1,n,1);for(int i=1,op,l,r;i<=q;i++){op=read(),l=read(),r=read();
//		cout<if(op==1) modify(1,n,1,l,r);else printf("%d\n",query(1,n,1,l,r));}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！