這題看起來好複雜QAQ
總之先相信它可以用線段樹維護吧(?)
這裡假設你已經建好波那契數列f的表了
假設我們建了一棵線段樹，存的值是f(1)*a1、f(2)*a2、f(3)*a3...
那麼，區間查詢和單點修改應該不會太難(就不提囉～
題目要求的是Sum{f(k)*a_(l+k),k=0~r-l}
而我們可以求出Sum{f(l+k)*a_(l+k),k=0~r-l}
可以怎麼利用呢？
為了方便說明，先定義g(i,l,r)=Sum{f(i+k)*a_(l+k),k=0~r-l}
所以題目要求g(0,l,r)，而我們可以求出g(l,l,r)
如果我們拿g(l,l,r)減掉g(l-1,l,r)會發生甚麼事呢？
這個東西變成了g(l-2,l,r)！
而我們現在知道了g(l-2,l,r)是啥，那就可以再拿g(l-1,l,r)減掉g(l-2,l,r)求出g(l-3,l,r)，然後是g(l-4,l,r)...，很快的(?)就可以得到g(0,l,r)了！
可以發現，假設g(l,l,r)是A，g(l-1,l,r)是B，l和r隨意，那麼可以透過以上相減關係，預處理出所有(x,y)使得g(i,l,r)=x*A+y*B(預處理的過程需要轉一些彎，詳情請參考code)
所以我們可以建兩棵線段樹分別維護g(l,l,r)和g(l-1,l,r)
就這樣，我們實現了O(log N)的單點修改和區間查詢g(0,l,r)
那區間修改呢？
首先，加入懶惰標記不難，重點是往下放的時候要怎麼維護？
其實，我們只需要關心區間和，因此，只要在往下放的時候分別將兩棵子樹增加「f的一段區間和*懶標的值」就好了(f的區間和可以用前綴和相減來處理)
講完了，別忘了還要Maintain XD
code:
#include<cstdio> #include<cassert> #include<vector> #include<utility> using namespace std; typedef long long LL; const LL MOD=1000000000LL; void Plus(LL &a,const LL &b){(a+=b)%=MOD;} int N,M; vector<LL>F,FSUM; LL GetF(const int i) { if(i<(int)F.size())return F[i]; F.push_back((GetF(i-2)+GetF(i-1))%MOD); FSUM.push_back(FSUM[i-1]+F[i]); return F[i]; } LL GetFSum(const int l,const int r){GetF(r);return FSUM[r]-FSUM[l-1];} struct SegTree { const int gap; vector<LL>sum,tag; SegTree(const int _gap):gap(_gap){} void Maintain(const int id){sum[id]=(sum[id*2]+sum[id*2+1])%MOD;} void PutDown(const int id,const int l,const int mid,const int r) { if(tag[id]==0LL)return; const LL v=tag[id];tag[id]=0LL; Plus(tag[id*2],v); Plus(tag[id*2+1],v); Plus(sum[id*2],v*GetFSum(gap+l,gap+mid)); Plus(sum[id*2+1],v*GetFSum(gap+mid+1,gap+r)); } void Build(const int id,const int l,const int r,const vector<LL>&s) { while((int)sum.size()<=id)sum.push_back(0LL),tag.push_back(0LL); tag[id]=0LL; if(l==r){sum[id]=(s[r]*GetF(gap+r))%MOD;return;} const int mid=(l+r)/2; Build(id*2,l,mid,s),Build(id*2+1,mid+1,r,s); Maintain(id); } void Add(const int id,const int l,const int r,const int bl,const int br,const LL &v) { if(r<bl||br<l)return; if(bl<=l&&r<=br){Plus(tag[id],v),Plus(sum[id],v*GetFSum(gap+l,gap+r));return;} const int mid=(l+r)/2; PutDown(id,l,mid,r); Add(id*2,l,mid,bl,br,v),Add(id*2+1,mid+1,r,bl,br,v); Maintain(id); } void Modify(const int id,const int l,const int r,const int loc,const LL &v) { if(l==r){assert(r==loc);sum[id]=(v*GetF(gap+r))%MOD;return;} const int mid=(l+r)/2; PutDown(id,l,mid,r); if(loc<=mid)Modify(id*2,l,mid,loc,v); else Modify(id*2+1,mid+1,r,loc,v); Maintain(id); } LL Query(const int id,const int l,const int r,const int bl,const int br) { if(r<bl||br<l)return 0LL; if(bl<=l&&r<=br)return sum[id]; const int mid=(l+r)/2; PutDown(id,l,mid,r); return (Query(id*2,l,mid,bl,br)+Query(id*2+1,mid+1,r,bl,br))%MOD; } }SEG1=SegTree(1),SEG2=SegTree(2); vector<pair<LL,LL> >COE; pair<LL,LL>GetCOE(const int i) { if(i<(int)COE.size())return COE[i]; const pair<LL,LL>p1=GetCOE(i-2),p2=GetCOE(i-1); COE.push_back(make_pair((p1.first-p2.first+MOD)%MOD,(p1.second-p2.second+MOD)%MOD)); return COE[i]; } int main() { // freopen("in.txt","r",stdin); F.push_back(1),F.push_back(1); FSUM.push_back(1),FSUM.push_back(2); COE.push_back(make_pair(1LL,0LL)),COE.push_back(make_pair(-1LL,1LL)); while(scanf("%d%d",&N,&M)==2) { if(true) { vector<LL>s; for(int i=0;i<N;i++) { static LL v;scanf("%lld",&v); s.push_back(v); } SEG1.Build(1,0,N-1,s),SEG2.Build(1,0,N-1,s); s.clear(),vector<LL>().swap(s); } for(int type;M--;) { scanf("%d",&type); switch(type) { case 1: { static int x,v; scanf("%d%d",&x,&v),x--; SEG1.Modify(1,0,N-1,x,v),SEG2.Modify(1,0,N-1,x,v); }break; case 2: { static int l,r; scanf("%d%d",&l,&r),l--,r--; const LL v1=SEG1.Query(1,0,N-1,l,r),v2=SEG2.Query(1,0,N-1,l,r); const pair<LL,LL>p=GetCOE(SEG1.gap+l); const LL ans=((p.first*v1+p.second*v2)%MOD+MOD)%MOD; printf("%lld\n",ans); }break; case 3: { static int l,r,d; scanf("%d%d%d",&l,&r,&d),l--,r--; SEG1.Add(1,0,N-1,l,r,d),SEG2.Add(1,0,N-1,l,r,d); }break; default:assert(0);break; } } break; } return 0; }
