fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fi first
  5. #define sc second
  6. #define ll long long
  7. #define pb push_back
  8. #define pii pair<int, int>
  9. #define ALL(a) a.begin(), a.end()
  10. #define REP(i, n) for(int i = 0; i < n; ++ i)
  11. #define FOR(i, a, b) for(int i = a; i <= b; ++ i)
  12. #define FORD(i, a, b) for(int i = a; i >= b; -- i)
  13.  
  14. const int N =  5e5 + 5;
  15. const int MOD = 1e9 + 7;
  16. const int INF = 1e9;
  17. const long long LINF = 1e18;
  18.  
  19. ll a[N], pw[N];
  20.  
  21. ll st[N][2];
  22.  
  23. int n, q;
  24.  
  25. ll sub(ll a, ll b)
  26. {
  27.     return (a % MOD - b % MOD + MOD) % MOD;
  28. }
  29.  
  30. ll add(ll a, ll b)
  31. {
  32.     return (a % MOD + b % MOD) % MOD;
  33. }
  34.  
  35. ll mul(ll a, ll b)
  36. {
  37.     return ((a % MOD) * (b % MOD)) % MOD;
  38. }
  39.  
  40.  
  41. void update(int pos, int val, int k, int id = 1, int l = 1, int r = n)
  42. {
  43.     if(pos < l || r < pos) return;
  44.     if(l == r)
  45.     {
  46.         st[id][k] = val;
  47.         return;
  48.     }
  49.     int m = l + r >> 1;
  50.     update(pos, val, k, id << 1, l, m);
  51.     update(pos, val, k, id << 1 | 1, m + 1, r);
  52.     st[id][k] = add(st[id << 1][k], st[id << 1 | 1][k]);
  53. }
  54.  
  55. int get(int lef, int rig, int k, int id = 1, int l = 1, int r = n)
  56. {
  57.     if(lef > r || rig < l) return 0;
  58.     if(lef <= l && r <= rig) return st[id][k];
  59.     int m = (l + r) >> 1;
  60.     return add(get(lef, rig, k, id << 1, l, m), get(lef, rig, k, id << 1 | 1, m + 1, r));
  61. }
  62.  
  63. void solve()
  64. {
  65.     cin >> n >> q;
  66.     FOR(i, 1, n) cin >> a[i];
  67.     pw[0] = 1;
  68.     FOR(i, 1, n) pw[i] = pw[i - 1] * 2 % MOD;
  69.     FOR(i, 1, n) update(i, mul(a[i], a[i]), 0);
  70.     FOR(i, 2, n) update(i, mul(a[i], a[i - 1]), 1);
  71.     while(q--)
  72.     {
  73.         int t, u, v;
  74.         cin >> t >> u >> v;
  75.         if(t == 1)
  76.         {
  77.             update(u, mul(v, v), 0);
  78.             a[u] = v;
  79.             if(u + 1 <= n) update(u + 1, mul(a[u + 1], v), 1);
  80.             if(u - 1 >= 1) update(u, mul(a[u - 1], v), 1);
  81.         }
  82.         else
  83.         {
  84.             ll x = get(u, v, 0), y = get(u + 1, v, 1);
  85.             cout << mul(pw[v - u], sub(x, y)) << "\n";
  86.         }
  87.     }
  88.  
  89. }
  90.  
  91. signed main()
  92. {
  93.     ios_base::sync_with_stdio(0); 
  94.     cin.tie(0);      cout.tie(0);
  95.  
  96.     solve();
  97.     return 0;
  98. }
  99.  
  100.  
Success #stdin #stdout 0.01s 5688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yvlcy9
language:
C++14 (clang 8.0)
created:
6 days ago
visibility:
public

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!