Description:

給出一個數列，每次可以選取一個區間，按順序加上第i個Fibonacci Numbers(斐波那契數)進行更新，也可以查詢某一個區間的總和。

Hint:

\(n \le 3*10^5\)

Solution:

數據結構結合數學

首先有公式 \(\sum _{i=1}^n fib(i)=fib(n+2)\)

且由于斐波那契的遞推是線性的,故所有的\(fib(i)\)都可以表示成\(a*fib(1)+b*fib(2)\)的形式

考慮用線段樹維護一個區間前兩個位置的系數,然后就可以做了

#include <map> #include <set> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define ls p<<1 #define rs p<<1|1 using namespace std; typedef long long ll; const ll mxn=1e6+5,mod=1e9+9; ll n,m,cnt,a[mxn],hd[mxn]; ll f[mxn],tr[mxn<<2],vis[mxn<<2],tag[mxn<<2][2];inline ll read() {char c=getchar(); ll x=0,f=1;while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}return x*f; } inline void chkmax(ll &x,ll y) {if(x<y) x=y;} inline void chkmin(ll &x,ll y) {if(x>y) x=y;}struct ed {ll to,nxt; }t[mxn<<1];inline void add(ll u,ll v) {t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt; }void push_up(ll p) {tr[p]=(tr[ls]+tr[rs])%mod; }struct ST {ll x,y; };ST fibget(ST tp,ll len) {ll c=tp.x*f[len]%mod+tp.y*f[len+1]%mod,d=tp.x*f[len+1]%mod+tp.y*f[len+2]%mod;return (ST) {c%mod,d%mod}; }ll fibcal(ll f1,ll f2,ll len) {ll res=0;if(len>=1) res=f1;if(len>=2) res=(res+f2)%mod;if(len>=3) res=(res+f2*(f[len+1]-2)%mod+f1*(f[len]-1)%mod+mod)%mod;//前兩項的系數的值,直接乘以當前f[i+1],f[i],計算出f[i+2]return res; }void push_down(ll p,ll l,ll r) {ll mid=(l+r)>>1;if(vis[p]) {ll &a=tag[p][0],&b=tag[p][1];tag[ls][0]=(tag[ls][0]+a)%mod;tag[ls][1]=(tag[ls][1]+b)%mod;tr[ls]=(tr[ls]+fibcal(a,b,mid-l+1))%mod;vis[ls]=1;ll c=a*f[mid-l]+b*f[mid-l+1],d=a*f[mid-l+1]+b*f[mid-l+2];c%=mod; d%=mod;tag[rs][0]=(tag[rs][0]+c)%mod;tag[rs][1]=(tag[rs][1]+d)%mod;tr[rs]=(tr[rs]+fibcal(c,d,r-mid))%mod;vis[rs]=1;vis[p]=tag[p][0]=tag[p][1]=0;} }void build(ll l,ll r,ll p) {if(l==r) {tr[p]=a[l]; return ;}ll mid=(l+r)>>1;build(l,mid,ls); build(mid+1,r,rs); push_up(p); }void modify(ll l,ll r,ll ql,ll qr,ll val1,ll val2,ll p) {if(ql<=l&&r<=qr) {tag[p][0]=(tag[p][0]+val1)%mod;tag[p][1]=(tag[p][1]+val2)%mod;tr[p]=(tr[p]+fibcal(val1,val2,r-l+1))%mod;vis[p]=1; return ;}ll mid=(l+r)>>1; push_down(p,l,r);if(qr<=mid) modify(l,mid,ql,qr,val1,val2,ls);else if(ql>mid) modify(mid+1,r,ql,qr,val1,val2,rs);else {modify(l,mid,ql,qr,val1,val2,ls);ST z=fibget((ST){val1,val2},mid-ql);modify(mid+1,r,mid+1/*詢問區間也要更改*/,qr,z.x,z.y,rs); //算出區間前兩個fib,貌似也可以用前綴和}push_up(p); }ll query(ll l,ll r,ll ql,ll qr,ll p) {if(ql<=l&&r<=qr) return tr[p];ll mid=(l+r)>>1; push_down(p,l,r); ll res=0;if(ql<=mid) res=(res+query(l,mid,ql,qr,ls))%mod;if(qr>mid) res=(res+query(mid+1,r,ql,qr,rs))%mod;return res; }void init() {n=read(); m=read(); ll x,y,opt; f[1]=f[2]=1; for(ll i=3;i<=n+4;++i) f[i]=(f[i-1]+f[i-2])%mod;for(ll i=1;i<=n;++i) a[i]=read()%mod; build(1,n,1);for(ll i=1;i<=m;++i) {opt=read(); x=read(); y=read();if(opt==1) modify(1,n,x,y,1,1,1);else printf("%lld\n",(query(1,n,x,y,1)+mod)%mod);} }int main() {init();return 0; }

轉載于:https://www.cnblogs.com/list1/p/10569701.html

總結

以上是生活随笔為你收集整理的[CF446C]DZY Loves Fibonacci Numbers的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。