Codeforces Round #FF (Div. 2)__E. DZY Loves Fibonacci Numbers (CF447) 线段树

http://codeforces.com/contest/447/problem/E

题意：给定一个数组， m次操作，

1 l r 表示区间修改，每次 a[i] + Fibonacci[i-l+]

2 l r 区间求和

每次修改操作，只需要记录每个点前两个值就可以了，后面的和以及孩子需要加的值都可以通过这两个求出来。推推公式就出来了。

注意溢出。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long LL;
  4 const int MAXN = 3e5+10;
  5 const int MOD = 1e9+9;
  6 LL sum[MAXN << 2], addv1[MAXN << 2], addv2[MAXN << 2];
  7 LL fib[MAXN], hhh[MAXN], fff[MAXN];
  8 void pre_solve() {
  9     fff[1] = 1;
 10     fff[2] = 0;
 11     fib[1] = fib[2] = 1;
 12     hhh[1] = 0;
 13     for (int i = 3; i < MAXN; i++) {
 14         fib[i] = (fib[i-1] + fib[i-2]) % MOD;
 15         fff[i] = (fff[i-1] + fff[i-2]) % MOD;
 16     }
 17     for (int i = 2; i < MAXN; i++) {
 18         hhh[i] = (fib[i-1] + hhh[i-1]) % MOD;
 19     }
 20 }
 21 void push_up(int pos) {
 22     sum[pos] = (sum[pos<<1] + sum[pos<<1|1]) % MOD;
 23 }
 24 void update_add(int l, int r, int pos, LL val1, LL val2) {
 25     addv1[pos] = (addv1[pos] + val1) % MOD;
 26     addv2[pos] = (addv2[pos] + val2) % MOD;
 27     int idx = (r - l + 1);
 28     sum[pos] = (sum[pos] + fib[idx] * val1 % MOD + hhh[idx] * val2 % MOD) % MOD;
 29 }
 30 void push_down(int l, int r, int pos) {
 31     int mid = (l + r) >> 1;
 32     update_add(l, mid, pos<<1, addv1[pos], addv2[pos]);
 33     update_add(mid+1, r, pos<<1|1, (fff[mid+1-l+1]*addv1[pos]+fib[mid+1-l]*addv2[pos])%MOD,
 34                (fff[mid+1-l+2]*addv1[pos]+fib[mid+1-l+1]*addv2[pos])%MOD);
 35     addv1[pos] = addv2[pos] = 0;
 36 }
 37 void build (int l, int r, int pos) {
 38     addv1[pos] = addv2[pos] = 0;
 39     if (l == r) {
 40         scanf ("%I64d", sum+pos);
 41         return ;
 42     }
 43     int mid = (l + r) >> 1;
 44     build(l, mid, pos<<1);
 45     build(mid+1, r, pos<<1|1);
 46     push_up(pos);
 47 }
 48 void update (int l, int r, int pos, int ua, int ub, LL x1, LL x2) {
 49     if (ua <= l && ub >= r) {
 50         update_add(l, r, pos, x1, x2);
 51         return ;
 52     }
 53     push_down(l, r, pos);
 54     int mid = (l + r) >> 1;
 55     if (ua <= mid) {
 56         update(l, mid, pos<<1, ua, ub, x1, x2);
 57     }
 58     if (ub > mid) {
 59         if (ua <= mid) {
 60             int tmp = max(l, ua);
 61             LL t1 = (fff[mid+1-tmp+1]*x1+fib[mid+1-tmp]*x2) % MOD;
 62             LL t2 = (fff[mid+1-tmp+2]*x1+fib[mid+1-tmp+1]*x2) % MOD;
 63             update(mid+1, r, pos<<1|1, ua, ub, t1, t2);
 64         } else {
 65             update(mid+1, r, pos<<1|1, ua, ub, x1, x2);
 66         }
 67     }
 68     push_up(pos);
 69 }
 70 LL query (int l, int r, int pos, int ua, int ub) {
 71     if (ua <= l && ub >= r) {
 72         return sum[pos];
 73     }
 74     push_down(l, r, pos);
 75     int mid = (l + r) >> 1;
 76     LL tmp = 0;
 77     if (ua <= mid)
 78     {
 79         tmp = (tmp + query(l, mid, pos<<1, ua, ub)) % MOD;
 80     }
 81     if (ub > mid)
 82     {
 83         tmp = (tmp + query(mid+1, r, pos<<1|1, ua, ub)) % MOD;
 84     }
 85 
 86     return tmp;
 87 }
 88 int main() {
 89 #ifndef ONLINE_JUDGE
 90     freopen("in.txt","r",stdin);
 91 #endif
 92     int n, m;
 93     pre_solve();
 94     while (~ scanf ("%d%d", &n, &m)) {
 95         build(1, n, 1);
 96         for (int i = 0; i < m; i++) {
 97             int op, u, v;
 98             scanf ("%d%d%d", &op, &u, &v);
 99             if (op == 1) {
100                 update(1, n, 1, u, v, fib[1], fib[2]);
101             } else {
102                 LL ans = query(1, n, 1, u, v);
103                 printf("%I64d
", ans);
104             }
105         }
106     }
107     return 0;
108 }