kuoying 2019-11-05
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; }