题意：给你一个长度为n的序列，然后有m次操作，操作分两种：
1，给出l，r，让你对该区间每一个数加上对应的斐波那契数列的数，举例，a[l]+1,a[l+1]+1,a[l+2]+2……。
2，给出l，r，让你对该区间的数求和，mod 1e9+9（tmd我写的1e9+7，debug浪费了一个小时，上床的时候都两点多了）
解法：首先对于一个类斐波那契数列，我们可以发下如下性质。
1,(n)=fab[n-2]*(1)+fab[n-1]*(2)
2,sum(n)如何求呢？结合上一条，然后列出表来，发现没有规律，然后我们做一个差分，就发现性质了。于是有
sum(n)=fab[n]+sfab[n-1]。同时这里要注意边界。
然后我们就能用线段树来维护了，懒标记开两个，分别维护第一个fab数和第二个fab数，当然尤其要注意边界，就是区间长度为1或2的时候，上面的规律不一定成立，特判就好啦。2点上床这个也贡献了一大部分。
// LUOGU_RID: 123922167 #include<bits/stdc++.h> #define de cout<<111<<"\n"; #define fi first #define se second #define ll long long #define kx(a,b) ((a*b)%mod) #define kplus(a,b) ((a+b)%mod) #define lowbit(x) x&(-x); #define lson k<<1,l,mid #define rson k<<1|1,mid+1,r #define lk k<<1 #define rk k<<1|1 #define up(a,b) ((a-1ll)/b+1ll) typedef __int128 Int; using namespace std; const int N=300010; //const ll mod=998244353; const int mod=1000000009; typedef pair<int,int> pii; ll fect[N], infect[N]; ll binpow(ll a,ll b,ll c){ ll ans=1; while(b){ if(b&1) ans=(Int)ans*a%c; a=(Int)a*a%c; b>>=1; } return ans;} int C(int a,int b){ return fect[a]*infect[b]%mod*infect[a-b]%mod;} void initzuhe(int n){ fect[0]=1;infect[0]=1; for(int i=1;i<=n;i++){ fect[i]=(fect[i-1]*i)%mod; } infect[n-1]=binpow(fect[n-1],mod-2ll,mod); for(int i=n-2;i>=1;i--) infect[i]=infect[i+1]*(i+1ll)%mod;} ll test[12]={2,3,5,7,11,13,17,19,23,29,31,37},maxn; bool check(ll a,ll n){ ll d=n-1,get=binpow(a,d,n); if(get!=1) return 1; while((d&1)^1) if(d>>=1,(get=binpow(a,d,n))==n-1) return 0; else if(get!=1) return 1; return 0;} bool miller_rabbin(ll n) { if(n<40){ for(int i=0;i<12;i++) if(test[i]==n) return 1; return 0; } for(int i=0;i<12;i++) if(check(test[i],n)) return 0; return 1;} ll gcd(ll a,ll b){ return !b?a:gcd(b,a%b);} inline ll f(ll x,ll c,ll n){ return ((Int)x*x+c)%n;} ll pollard_rho(ll x){ ll s=0,t=0,c=1ll*rand()%(x-1)+1,val=1; for(int i=1;;i<<=1,s=t,val=1){ for(int j=1;j<=i;j++){ t=f(t,c,x); val=(Int)val*abs(t-s)%x; if(!(j%127)){ ll d=gcd(val,x); if(d>1) return d; } } ll d=gcd(val,x); if(d>1) return d; }} ll x,y; ll exgcd(ll a,ll b,ll &x,ll &y){ if(b==0){ x=1ll,y=0ll; return a; } ll temp=exgcd(b,a%b,x,y); ll z=x;x=y; y=z-a/b*y; return temp; } ll fab[300010],sfab[300010]; struct kkk{ ll a,x,y; }seg[N<<2]; void build(int k,int l,int r){ seg[k].x=seg[k].y=0; if(l==r){cin>>seg[k].a;return ;} int mid=l+r>>1; build(lson),build(rson); seg[k].a=kplus(seg[lk].a,seg[rk].a); } int calrf(int xx,int yy,int len){ if(len==1)return xx; if(len==2)return yy; return kplus(kx(fab[len-2],xx),kx(fab[len-1],yy)); } int calsum(int xx,int yy,int len){ if(len==1)return xx; if(len==2)return kplus(xx,yy); return kplus(kx(xx,fab[len]),kx(yy,sfab[len-1])); } void pushdown(int k,int l,int r){ if(l==r)return ; int mid=l+r>>1; ll lenl=mid-l+1,lenr=r-mid; ll r1=calrf(seg[k].x,seg[k].y,lenl+1); ll r2=calrf(seg[k].x,seg[k].y,lenl+2); ll l1=seg[k].x,l2=seg[k].y; seg[lk].a=kplus(seg[lk].a,calsum(l1,l2,lenl)); seg[rk].a=kplus(seg[rk].a,calsum(r1,r2,lenr)); seg[lk].x=kplus(seg[lk].x,l1);seg[lk].y=kplus(seg[lk].y,l2); seg[rk].x=kplus(seg[rk].x,r1);seg[rk].y=kplus(seg[rk].y,r2); seg[k].x=0,seg[k].y=0; } void update(int k,int l,int r,int x,int y){ pushdown(k,l,r); if(x<=l&&r<=y){ ll len=r-l+1; seg[k].a=kplus(seg[k].a,calsum(fab[l-x+1],fab[l-x+2],len)); seg[k].x=fab[l-x+1]; seg[k].y=fab[l-x+2]; return ; } int mid=l+r>>1; if(x<=mid)update(lson,x,y); if(y>mid)update(rson,x,y); seg[k].a=kplus(seg[lk].a,seg[rk].a); } ll query(int k,int l,int r,int x,int y){ pushdown(k,l,r); if(x<=l&&r<=y){ return seg[k].a; } int mid=l+r>>1; ll res=0ll; if(x<=mid)res=kplus(res,query(lson,x,y)); if(y>mid)res=kplus(res,query(rson,x,y)); return res; } void bugseg(int k,int l,int r){ cout<<k<<" "<<l<<" "<<r<<" "<<seg[k].a<<" "<<seg[k].x<<" "<<seg[k].y<<"\n"; if(l==r)return ; int mid=l+r>>1; bugseg(lson);bugseg(rson); } void solve(){ int n,m;cin>>n>>m; build(1,1,n); while(m--){ int op;cin>>op; if(op==1){ int x,y;cin>>x>>y; update(1,1,n,x,y); } else{ int x,y;cin>>x>>y; cout<<query(1,1,n,x,y)<<"\n"; } //bugseg(1,1,n); } } signed main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); srand((unsigned)time(NULL)); fab[1]=1ll;fab[2]=1ll; sfab[1]=1ll;sfab[2]=2ll; for(int i=3;i<=300000;i++){ fab[i]=kplus(fab[i-1],fab[i-2]); sfab[i]=kplus(sfab[i-1],fab[i]); } //int t;cin>>t;while(t--) solve(); }