CF446C DZY Loves Fibonacci Numbers <线段树>

Problem

DZY Loves Fibonacci Numbers

$\mathrm{Time\;limit:\;4\;Sec}$
$\mathrm{Memory\;limit:\;256\;MB}$

Description

In mathematical terms, the sequence $F_n$ of $Fibonacci$ $numbers$ is defined by the recurrence relation $F_1 = 1,F_2 = 1,F_3=F_1+F_2=3,\cdots F_n = F_{n-1}+F_{n-2}$.
$\mathrm{DZY}$ loves Fibonacci numbers very much. Today $\mathrm{DZY}$ gives you an array consisting of $n$ integers: $a_1, a_2,\cdots,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\le i\le r$.
2. Format of the query “$2$ $l$ $r$”. In reply to the query you should output the value of $\sum_{i=l}^{r}{a_i}$ modulo $10^9+9$.

Help $\mathrm{DZY}$ reply to all the queries.

Input

The first line of the input contains two integers $n$ and $m$ $(1 \le n, m \le 3\times 10^5)$. The second line contains n integers $a_1, a_2, \cdots, a_n (1 ≤ a_i \le10^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 \le l \le r \le n$ holds.

Output

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

Example

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

给出一个长为$3\times 10^5$级别的初始数组，要求维护两种操作：

1. 将$a_l \sim a_r$中的每个数对应加上从$Fib_1\sim Fib_{l-r+1}$的斐波那契数，即使$a_i(i\in[l,r])$加上$Fib_{i-l+1}$
2. 询问$\sum_{i=l}^{r}{a_i}$模$10^9+9$的值

Solution

不难想到此题需要用线段树维护。不过难点在于如何合并标记。

初步想法是每次打标记时记录下此区间是从斐波那契数列的多少项开始一一对应地加进去，不过这样是无法合并标记的，每个结点只能有一个标记，可以被卡成$O(n^2\log n)$。

考虑把标记换一种存法。对于一个数列$x_1=a,x_2=b,x_3=a+b,x_4=a+b\times 2,\cdots x_n=x_{n-1}+x_{n-2}$，我们将其称为一个“伪斐波那契数列”，不难发现其等于几个斐波那契数列的子序列之和，即在原题中，不管如何加，每个区间最后加的数列都是一个伪斐波那契数列。而此序列可以仅通过最前面的两项$a$和$b$推出后面的任意项以及前若干项之和，即

$$\begin{aligned} x_n &= x_{n-1}+x_{n-2}\\ &= 2\times x_{n-2}+x_{n-3}\\ &= 3\times x_{n-3}+2\times x_{n-4}\\ &= Fib_{n-2}\times x_1+Fib_{n-1}\times x_2\\ \sum_{i=1}^{n}{x_i} &= x_1+x_2+x_3+\cdots x_n\\ &= x_1+x_2+x_2+x_3+\cdots +x_n-x_2\\ &= x_3+x_4+x_4+x_5+\cdots +x_n-x_2\\ &= x_5+x_6+x_6+x_7+\cdots +x_n-x_2\\ &= x_{n-2}+x_{n-1}+x_{n-1}+x_{n}-x_2\\ &= x_n+x_{n+1}-x_2\\ &= x_{n+2}-x_{2} \end{aligned}$$

用这两个公式我们可以$O(1)$计算任意项及前任意项的和。
每个标记为一个数对$(a,b)$，那么合并标记的时候将两个标记的$a$和$b$分别相加，得到$(a_1+a_2,b_1+b_2)$即可。
总时间复杂度$O(n\log n)$。

Code

#include <bits/stdc++.h>
#define MAX_N 1000000
#define mid ((s+t)>>1)
#define MOD 1000000009
using namespace std;
typedef long long lnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;    lnt fib[MAX_N+5] = {0LL, 1LL};
struct node {lnt c, f1, f2;} tr[(MAX_N<<2)+5];
lnt fn(lnt f1, lnt f2, int len) {return len == 1 ? f1 : (len == 2 ? f2 : (f1*fib[len-2]%MOD+f2*fib[len-1]%MOD)%MOD);}
lnt sum(lnt f1, lnt f2, int len) {return len == 1 ? f1 : (len == 2 ? (f1+f2)%MOD : (fn(f1, f2, len+2)-f2+MOD)%MOD);}
void updata(int v) {tr[v].c = (tr[v<<1].c+tr[v<<1|1].c)%MOD;}
void downtag(int v, int s, int t) {
    if (!tr[v].f1) return;
    lnt lf1 = tr[v].f1, lf2 = tr[v].f2, rf1 = fn(lf1, lf2, mid-s+2), rf2 = fn(lf1, lf2, mid-s+3);
    (tr[v<<1].f1 += lf1) %= MOD, (tr[v<<1].f2 += lf2) %= MOD, (tr[v<<1].c += sum(lf1, lf2, mid-s+1)) %= MOD;
    (tr[v<<1|1].f1 += rf1) %= MOD, (tr[v<<1|1].f2 += rf2) %= MOD, (tr[v<<1|1].c += sum(rf1, rf2, t-mid)) %= MOD;
    tr[v].f1 = tr[v].f2 = 0;
}
void build(int v, int s, int t) {
    if (s == t) {read(tr[v].c); return;}
    build(v<<1, s, mid), build(v<<1|1, mid+1, t);
    updata(v);
}
void modify(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) {
        (tr[v].f1 += fib[s-l+1]) %= MOD, (tr[v].f2 += fib[s-l+2]) %= MOD;
        (tr[v].c += sum(fib[s-l+1], fib[s-l+2], t-s+1)) %= MOD;	return;
    }
    downtag(v, s, t);
    if (l <= mid) modify(v<<1, s, mid, l, r);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r);
    updata(v);
}
lnt query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v].c;
    lnt ret = 0;	downtag(v, s, t);
    if (l <= mid) (ret += query(v<<1, s, mid, l, r)) %= MOD;
    if (r >= mid+1) (ret += query(v<<1|1, mid+1, t, l, r)) %= MOD;
    updata(v);	return ret;
}
void init() {for (int i = 2; i <= MAX_N; i++) fib[i] = (fib[i-2]+fib[i-1])%MOD;}
int main() {
    read(n), read(m), init(), build(1, 1, n);
    while (m--) {
        int opt, l, r;	read(opt), read(l), read(r);
        if (opt == 1) modify(1, 1, n, l, r);
        else printf("%I64d\n", query(1, 1, n, l, r));
    }
    return 0;
}