codeforces 446C DZY Loves Fibonacci Numbers

​​http://www.elijahqi.win/2018/03/03/codeforces-446c/​​​

題意翻譯

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

感謝@char32_t 提供的翻譯

題目描述

In mathematical terms, the sequence

Fn F_{n}

F

n

​

of Fibonacci numbers is defined by the recurrence relation

F1=1;F2=1;Fn=Fn−1+Fn−2(n>2).

F

1

=

1

;

F

2

=

1

;

F

n

=

F

n

−

1

+

F

n

−

2

(

n

>

2

)

.

DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of

n n

n integers:

a1,a2,…,an a_{1},a_{2},…,a_{n}

a

1

​

,a

2

​

,…,a

n

​

. Moreover, there are

m m

m queries, each query has one of the two types:

Format of the query ”

1 l r 1\ l\ r

1 l r “. In reply to the query, you need to add

Fi−l+1 F_{i-l+1}

F

i−l+1

​

to each element

ai a_{i}

a

i

​

, where

l<=i<=r l<=i<=r

l<=i<=r .

Format of the query ”

2 l r 2\ l\ r

2 l r “. In reply to the query you should output the value of modulo 1000000009(109+9)

1000000009

(

10

9

+

9

)

.

Help DZY reply to all the queries.

輸入輸出格式

輸入格式：

The first line of the input contains two integers

n n

n and

m m

m (

1<=n,m<=300000 1<=n,m<=300000

1<=n,m<=300000 ). The second line contains

n n

n integers a1,a2,...,an(1<=ai<=109)

a

1

,

a

2

,

.

.

.

,

a

n

(

1

<=

a

i

<=

10

9

)

— initial array

a a

a .

Then,

m m

m lines follow. A single line describes a single query in the format given in the statement. It is guaranteed that for each query inequality

1<=l<=r<=n 1<=l<=r<=n

1<=l<=r<=n holds.

輸出格式：

#include<cstdio>
#include<algorithm>
#define mod 1000000009
#define N 330000
#define ll long long
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
    return x*f;
}
struct node{
    int sum,fa,fb;int left,right;
}tree[N<<1];
int n,m,a[N],f[N],num,root;
inline int calc_kth(int a,int b,int k){
    if (k==1) return a;if (k==2) return b;
    return ((ll)a*f[k-2]+(ll)b*f[k-1])%mod;
}
inline void update(int x){
    int l=tree[x].left,r=tree[x].right;
    tree[x].sum=(tree[l].sum+tree[r].sum)%mod;
}
inline void build(int &x,int l,int r){
    x=++num;int mid=l+r>>1;if (l==r) {tree[x].sum=a[l];return;}
    build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);update(x);
}
inline int getsum(int a,int b,int k){
    if (k==1) return a;if(k==2) return (a+b)%mod;
    return (calc_kth(a,b,k+2)-b+mod)%mod;
}
inline void pushdown(int x,int l,int r){
    if (!tree[x].fa) return;int mid=l+r>>1;
    int lc=tree[x].left,rc=tree[x].right,a,b;
    (tree[lc].fa+=tree[x].fa)%=mod;(tree[lc].fb+=tree[x].fb)%=mod;
    (tree[lc].sum+=getsum(tree[x].fa,tree[x].fb,mid-l+1))%=mod;
    a=calc_kth(tree[x].fa,tree[x].fb,mid-l+2);
    b=calc_kth(tree[x].fa,tree[x].fb,mid-l+3);
    (tree[rc].fa+=(a))%=mod;
    (tree[rc].fb+=(b))%=mod;
    (tree[rc].sum+=getsum(a,b,r-mid))%=mod;
    tree[x].fa=tree[x].fb=0;
}
inline void change(int x,int len,int a,int b){
    (tree[x].fa+=a)%=mod;(tree[x].fb+=b)%=mod;
    (tree[x].sum+=getsum(a,b,len))%=mod;
}
inline void insert1(int x,int l,int r,int l1,int r1){
    if (l1<=l&&r1>=r){change(x,r-l+1,f[l-l1+1],f[l-l1+2]);return;}
    int mid=l+r>>1;pushdown(x,l,r);
    if(l1<=mid) insert1(tree[x].left,l,mid,l1,r1);
    if (r1>mid) insert1(tree[x].right,mid+1,r,l1,r1);update(x);
}
inline int query(int x,int l,int r,int l1,int r1){
    if (l1<=l&&r1>=r) return tree[x].sum;int mid=l+r>>1;ll tmp=0;pushdown(x,l,r);
    if (l1<=mid) tmp+=query(tree[x].left,l,mid,l1,r1);
    if (r1>mid) tmp+=query(tree[x].right,mid+1,r,l1,r1);return tmp%mod;
}
inline void print(int x,int l,int r){
    pushdown(x,l,r);int mid=l+r>>1;
    if(tree[x].left) print(tree[x].left,l,mid);
    printf("%d %d %d\n",l,r,tree[x].sum);
    if (tree[x].right) print(tree[x].right,mid+1,r);
}
int main(){
    freopen("cf446c.in","r",stdin);
    n=read();m=read();for (int i=1;i<=n;++i) a[i]=read();
    f[1]=f[2]=1;for (int i=3;i<=n+2;++i) f[i]=(f[i-1]+f[i-2])%mod;build(root,1,n);
    //for (int i=1;i<=n;++i) printf("%d,f[i]);puts("" );
    while(m--){
        int op=read(),l=read(),r=read(); 
        if(op==1) insert1(root,1,n,l,r);
        if(op==2) {
        //  if (query(root,1,n,l,r)==74) printf("%d %d\n",l,r);
            printf("%d\n",query(root,1,n,l,r));
        }//print(root,1,n);puts("----------");
    }
    return 0;
}
/*
488
563
105
69
71
256
210
175
373
217
*/