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

This blog post is only available in Simplified Chinse.

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:

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$ .
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

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。可以发现以下两个结论：

如果只存数列的前两项 a 和 b，可以推出这个数列，包括可以 $\Theta(1)$ 推出第 $n$ 项和前 $n$ 项之和。列表可以发现规律：

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$ 项）

如何 $\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 如果直接累计不会有问题。

这样我们可以写一个 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:

我的博客并没有弃坑！

1/29/2019