fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int mod  = 1e9 + 9;
  6. const int maxN = 3e5 + 10;
  7.  
  8. int n, m;
  9. int a[maxN], fibo[maxN], st[4 * maxN];
  10. pair <int, int> lazy[4 * maxN];
  11.  
  12. void add(int &x, int y) {
  13.     x += y;
  14.     if (x > mod) x -= mod;
  15. }
  16.  
  17. void build(int id, int l, int r) {
  18.     if (l == r) {
  19.         st[id] = a[l]; 
  20.         return;
  21.     }
  22.     int mid = (l + r) >> 1;
  23.     build(id << 1, l, mid);
  24.     build(id << 1 | 1, mid + 1, r);
  25.     st[id] = (st[id << 1] + st[id << 1 | 1]) % mod;
  26. }
  27.  
  28. void fix(int id, int l, int r) {
  29.     if (!lazy[id].first && !lazy[id].second) return;
  30.  
  31.     long long a = lazy[id].first;
  32.     long long b = lazy[id].second;
  33.     int tmp = (r - l + 1) + 2;
  34.     add(st[id], (b * fibo[tmp - 1] + a * fibo[tmp - 2] - b) % mod);
  35.  
  36.     if (l != r) {
  37.         int mid = (r - l) >> 1;
  38.         add(lazy[id << 1].first , lazy[id].first);
  39.         add(lazy[id << 1].second, lazy[id].second);
  40.         add(lazy[id << 1 | 1].first , (b * fibo[mid + 1] + a * fibo[mid]) % mod);
  41.         add(lazy[id << 1 | 1].second, (b * fibo[mid + 2] + a * fibo[mid + 1]) % mod);
  42.     }
  43.     lazy[id] = {0, 0};
  44. }
  45.  
  46. void update(int id, int l, int r, int u, int v) {
  47.     fix(id, l, r);
  48.     if (l >  v || r <  u) return;
  49.     if (l >= u && r <= v) {
  50.         int tmp = l - u + 1;
  51.         add(lazy[id].first , fibo[tmp]);
  52.         add(lazy[id].second, fibo[tmp + 1]);
  53.         fix(id, l, r);
  54.         return;
  55.     }
  56.     int mid = (l + r) >> 1;
  57.     update(id << 1, l, mid, u, v);
  58.     update(id << 1 | 1, mid + 1, r, u, v);
  59.     st[id] = (st[id << 1] + st[id << 1 | 1]) % mod;
  60. }
  61.  
  62. int get(int id, int l, int r, int u, int v) {
  63.     fix(id, l, r);
  64.     if (l >  v || r <  u) return 0;
  65.     if (l >= u && r <= v) return st[id];
  66.  
  67.     int mid = (l + r) >> 1;
  68.     int g1 = get(id << 1, l, mid, u, v);
  69.     int g2 = get(id << 1 | 1, mid + 1, r, u, v);
  70.     return (g1 + g2) % mod;
  71. }
  72.  
  73. main() {
  74.     cin >> n >> m;
  75.     for (int i = 1; i <= n; ++i) cin >> a[i];
  76.     build(1, 1, n);
  77.  
  78.     fibo[1] = fibo[2] = 1;
  79.     for (int i = 3; i <= n + 2; ++i) 
  80.         fibo[i] = (fibo[i - 1] + fibo[i - 2]) % mod;
  81.  
  82.     while (m--) {
  83.         int t, l, r; 
  84.         cin >> t >> l >> r; 
  85.         if (t == 1) update(1, 1, n, l, r);
  86.         else cout << get(1, 1, n, l, r) << '\n';
  87.     }
  88. }
Success #stdin #stdout 0.01s 7656KB
comments (?)
stdin
copy 
4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3
stdout
copy 
17
12
https://ideone.com/zRN7N1
language:
C++ 4.3.2 (gcc-4.3.2)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!