# CodeForces 447E - DZY Loves Fibonacci Numbers 题解：线段树

2019 年 1 月 29 日 12:01

## Description

In mathematical terms, the sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation

$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 integers: $a_1, a_2, \dots, a_n$. Moreover, there are $m$ queries, each query has one of the two types:

1. Format of the query "1 l r". In reply to the query, you need to add $F_{i - l + 1}$ to each element $a_i$, where $l \leq i \leq r$.
2. Format of the query "2 l r". In reply to the query you should output the value of modulo $1000000009 (10^9 + 9)$.

Help DZY reply to all the queries.

• time limit per test: 4 seconds
• memory limit per test: 256 megabytes
• input: standard input
• output: standard output

## Input

The first line of the input contains two integers $n$ and $m (1 ≤ n, m ≤ 300000)$. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 ≤ a_i ≤ 10^9$) — initial array $a$.

Then, $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$ holds.

## Output

For each query of the second type, print the value of the sum on a single line.

## Examples

input

4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3



output

17
12



## Note

After the first query, $a = [2, 3, 5, 7]$.

For the second query, $sum = 2 + 3 + 5 + 7 = 17$.

After the third query, $a = [2, 4, 6, 9]$.

For the fourth query, $sum = 2 + 4 + 6 = 12$.

## Analysis

• 如果只存数列的前两项 a 和 b，可以推出这个数列，包括可以 $\Theta(1)$ 推出第 $n$ 项和前 $n$ 项之和。列表可以发现规律：
12345...n
aba+ba+2b2a+3b...$F_{n-2}a+F_{n-1}b$

$F_i$ 表示斐波那契数列第 $i$ 项）

• 如何 $\Theta(1)$ 求和？

$Sum = \sum_{i=1}^{n} a\ast F_{n-2}+b\ast F_{n-1} = a\ast sum_{n-2} +b\ast sum_{n-1}+a$

$sum_i$ 表示斐波那契前 $i$ 项前缀和）

• 这样的数列具有可加性，也就是 lazy tag 如果直接累计不会有问题。

namespace Fibonacci{
int f[maxn],sum[maxn];

inline void build(){
f[1]=f[2]=1;sum[1]=1;sum[2]=2;
for (int i=3;i<=N;i++) f[i]=(f[i-1]+f[i-2])%tt,sum[i]=(sum[i-1]+f[i])%tt;
}

inline int query(int a,int b,int n){
if (n==0) return 0; else
if (n==1) return a%tt; else
if (n==2) return b%tt; else
return (f[n-2]*a%tt+f[n-1]*b%tt)%tt;
}

inline int get_sum(int a,int b,int n){
if (n==0) return 0; else
if (n==1) return a%tt; else
if (n==2) return (a+b)%tt; else
return (a*sum[n-2]%tt+b*sum[n-1]%tt+a%tt)%tt;
}
}


## Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
#define int long long

const int maxn=300005,N=300000;
const int tt=1000000009;

int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}

inline void plus_mod(int &x,int y){
x=(x+y)%tt;
}

namespace Fibonacci{
int f[maxn],sum[maxn];

inline void build(){
f[1]=f[2]=1;sum[1]=1;sum[2]=2;
for (int i=3;i<=N;i++) f[i]=(f[i-1]+f[i-2])%tt,sum[i]=(sum[i-1]+f[i])%tt;
}

inline int query(int a,int b,int n){
if (n==0) return 0; else
if (n==1) return a%tt; else
if (n==2) return b%tt; else
return (f[n-2]*a%tt+f[n-1]*b%tt)%tt;
}

inline int get_sum(int a,int b,int n){
if (n==0) return 0; else
if (n==1) return a%tt; else
if (n==2) return (a+b)%tt; else
return (a*sum[n-2]%tt+b*sum[n-1]%tt+a%tt)%tt;
}
}

#define ls ((p<<1))
#define rs ((p<<1)+1)
#define mid (((tr-tl)>>1)+tl)

namespace SegmentTree{
int sum[maxn*4];
int tag_a[maxn*4],tag_b[maxn*4];

inline void push_down(int tl,int tr,int p){
int as=Fibonacci::query(tag_a[p],tag_b[p],mid+1-tl+1);
int bs=Fibonacci::query(tag_a[p],tag_b[p],mid+2-tl+1);
plus_mod(sum[ls],Fibonacci::get_sum(tag_a[p],tag_b[p],mid-tl+1));
plus_mod(sum[rs],Fibonacci::get_sum(as,bs,tr-(mid+1)+1));
plus_mod(tag_a[ls],tag_a[p]); plus_mod(tag_b[ls],tag_b[p]);
plus_mod(tag_a[rs],as); plus_mod(tag_b[rs],bs);
tag_a[p]=tag_b[p]=0;
}

inline void update(int sl,int sr,int tl,int tr,int p,int a,int b,int st){
if (sl<=tl && tr<=sr){
plus_mod(sum[p],Fibonacci::get_sum(a,b,tr-tl+1));
plus_mod(tag_a[p],a); plus_mod(tag_b[p],b);
return;
}
push_down(tl,tr,p);
int as,bs;
if (sl<=mid  ){
update(sl,sr,tl,mid,ls,a,b,st);
as=Fibonacci::query(a,b,mid+1-max(sl,tl)+1);
bs=Fibonacci::query(a,b,mid+2-max(sl,tl)+1);
} else {
as=a;bs=b;
}
if (mid+1<=sr) update(sl,sr,mid+1,tr,rs,as,bs,mid+1);
sum[p]=(sum[ls]+sum[rs])%tt;
}

inline int query(int sl,int sr,int tl,int tr,int p){
if (sl<=tl && tr<=sr) return sum[p];
push_down(tl,tr,p);
int ret=0;
if (sl<=mid  ) plus_mod(ret,query(sl,sr,tl,mid,ls));
if (mid+1<=sr) plus_mod(ret,query(sl,sr,mid+1,tr,rs));
return ret%tt;
}
}

int n,m;
int a[maxn],sum[maxn];

signed main(){
Fibonacci::build();
for (int i=1;i<=m;i++){
if (opt==1){
SegmentTree::update(x,y,1,n,1,1,1,x);
} else if (opt==2){
int ans=SegmentTree::query(x,y,1,n,1);
printf("%lld\n",(ans+sum[y]-sum[x-1]+tt)%tt);
}
}
return 0;
}