CodeForces 447E – DZY Loves Fibonacci Numbers 题解:线段树

/ 0评 / 1

Description

Link

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.

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.

Translation

题意:给出一个数组 a_i,现在有 m 个操作,每个操作给出 L 和 R,可能是将这个区间里所有数字加上斐波那契数列对应的项(第 i 个数字加 F_{i-L+1}),或者是查询这个区间所有值之和。

Analysis

肯定想到用线段树。但是一般的线段树只能维护加和,需要考虑如何对斐波那契数列也构造 lazy tag。可以发现以下两个结论:

1 2 3 4 5 ... n
a b a+b a+2b 2a+3b ... F_{n-2}a+F_{n-1}b

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

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 项前缀和)

这样我们可以写一个 Fibonacci 相关的模块:

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;
    }
}

那么接下来我们可以写一个变异的线段树了。打两个烂标记 tag_a 和 tag_b 分别表示数列第一项和第二项。需要注意的是,update 操作时在向下“分割”的时候需要特别注意下数列左端点的两种情况。

建树是不需要的,可以假装原来的序列全是 0,询问的时候再前缀和累加。可以少写一个 build 了~

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;

inline int read(){
    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();
    n=read();m=read();
    for (int i=1;i<=n;i++) a[i]=read(),sum[i]=(sum[i-1]+a[i])%tt;
    for (int i=1;i<=m;i++){
        int opt=read(),x=read(),y=read();
        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;
}

颓了半个学期文化课,该回来颓 OI 了 :new_moon_with_face:

我的博客并没有弃坑!


知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/cf447e/


发表评论

电子邮件地址不会被公开。 必填项已用*标注