CF446C DZY Loves Fibonacci Numbers 线段树 + 数学
code:
#include <bits/stdc++.h> #define N 400004 #define LL long long #define lson now<<1 #define rson now<<1|1 #define setIO(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; const LL mod=1000000009; int n,m; LL fib[N<<1],sum[N<<1]; struct node { LL f1,f2,sum; int l,r,len; }t[N<<2]; void build(int l,int r,int now) { t[now].l=l; t[now].r=r; t[now].len=r-l+1; if(l==r) return ; int mid=(l+r)>>1; if(l<=mid) build(l,mid,lson); if(r>mid) build(mid+1,r,rson); } void mark(int now,LL f1,LL f2) { (t[now].f1+=f1)%=mod; (t[now].f2+=f2)%=mod; (t[now].sum+=f1*fib[t[now].len]%mod+f2*fib[t[now].len+1]%mod-f2+mod)%=mod; } void pushup(int now) { t[now].sum=(t[lson].sum+t[rson].sum)%mod; } void pushdown(int now) { if(t[now].f1==0&&t[now].f2==0) return; int mid=(t[now].l+t[now].r)>>1; mark(lson,t[now].f1,t[now].f2); if(t[now].r>mid) mark(rson,t[now].f1*fib[t[lson].len-1]%mod+t[now].f2*fib[t[lson].len]%mod,t[now].f1*fib[t[lson].len]%mod+t[now].f2*fib[t[lson].len+1]%mod); t[now].f1=t[now].f2=0; } void update(int l,int r,int now,int L,int R) { if(l>=L&&r<=R) { mark(now,fib[l-L+1],fib[l-L+2]); return; } pushdown(now); int mid=(l+r)>>1; if(L<=mid) update(l,mid,lson,L,R); if(R>mid) update(mid+1,r,rson,L,R); pushup(now); } LL query(int l,int r,int now,int L,int R) { if(l>=L&&r<=R) { return t[now].sum; } pushdown(now); int mid=(l+r)>>1; LL re=0ll; if(L<=mid) re+=query(l,mid,lson,L,R); if(R>mid) re+=query(mid+1,r,rson,L,R); return re%mod; } int main() { // setIO("input"); int i,j; scanf("%d%d",&n,&m); fib[1]=fib[2]=1; for(i=3;i<N;++i) fib[i]=(fib[i-1]+fib[i-2])%mod; for(i=1;i<=n;++i) scanf("%lld",&sum[i]), (sum[i]+=sum[i-1])%=mod; build(1,n,1); for(i=1;i<=m;++i) { int opt,l,r; scanf("%d%d%d",&opt,&l,&r); if(opt==1) update(1,n,1,l,r); else printf("%lld\n",(query(1,n,1,l,r)+sum[r]-sum[l-1]+mod*2)%mod); } return 0; }
相关推荐
starletkiss 2020-05-27
starletkiss 2020-05-26
xceman 2020-10-13
算法与数学之美 2020-10-07
Anscor 2020-10-05
liwg0 2020-09-08
数学爱好者 2020-08-31
thermodynamicB 2020-08-11
夕加加 2020-07-20
willowwgx 2020-07-18
kuoying 2020-07-16
Anscor 2020-07-14
starletkiss 2020-07-08
kingzone 2020-06-27
xceman 2020-06-27
算法与数学之美 2020-06-21
kuoying 2020-06-21