ProgMe

Untitled

Jan 5th, 2024
742
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int int64_t
  3.  
  4. using namespace std;
  5.  
  6. struct vertex {
  7.     int sum = 0;
  8. };
  9.  
  10. ostream& operator << (ostream& out, const vertex& v) {
  11.     return out << v.sum;
  12. }
  13.  
  14. const int N = 1e5 + 1;
  15.  
  16. array<int, N> a;
  17. array<vertex, 4 * N> t;
  18.  
  19. vertex merge(vertex l, vertex r) {
  20.     vertex cur{};
  21.     cur.sum = l.sum + r.sum;
  22.  
  23.     return cur;
  24. }
  25.  
  26. void build(int v, int tl, int tr) {
  27.     if (tr - tl == 1) {
  28.         t[v].sum = a[tl];
  29.         return;
  30.     }
  31.  
  32.     int tm = (tl + tr) / 2;
  33.     build(v * 2, tl, tm);
  34.     build(v * 2 + 1, tm, tr);
  35.  
  36.     t[v] = merge(t[v * 2], t[v * 2 + 1]);
  37. }
  38.  
  39. void update(int v, int tl, int tr, int i, int x) {
  40.     if (tr - tl == 1) {
  41.         t[v].sum = x;
  42.         return;
  43.     }
  44.  
  45.     int tm = (tl + tr) / 2;
  46.  
  47.     if (i < tm) {
  48.         update(v * 2, tl, tm, i, x);
  49.     } else {
  50.         update(v * 2 + 1, tm, tr, i, x);
  51.     }
  52.  
  53.     t[v] = merge(t[v * 2], t[v * 2 + 1]);
  54. }
  55.  
  56. vertex get(int v, int tl, int tr, int l, int r) {
  57.     if (r <= tl || l >= tr) {
  58.         return vertex(0);
  59.     }
  60.  
  61.     if (l <= tl && r >= tr) {
  62.         return t[v];
  63.     }
  64.  
  65.     int tm = (tl + tr) / 2;
  66.  
  67.     return merge(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm, tr, l, r));
  68. }
  69.  
  70. int32_t main() {
  71.     int n;
  72.     cin >> n;
  73.  
  74.     for (int i = 0; i < n; i++) {
  75.         cin >> a[i];
  76.     }
  77.  
  78.     build(1, 0, n);
  79.  
  80.     int q;
  81.     cin >> q;
  82.     while (q--) {
  83.         char c;
  84.         cin >> c;
  85.  
  86.         if (c == 'u') {
  87.             int i, x;
  88.             cin >> i >> x;
  89.             i--;
  90.  
  91.             update(1, 0, n, i, x);
  92.         } else {
  93.             int l, r;
  94.             cin >> l >> r;
  95.             l--;
  96.  
  97.             cout << get(1, 0, n, l, r) << ' ';
  98.         }
  99.     }
  100. }
  101.  
Advertisement
Add Comment
Please, Sign In to add comment