Advertisement
Guest User

Untitled

a guest
Oct 14th, 2019
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
  6.  
  7. const int SIZE = (1 << 17);
  8. int a[100100];
  9. int tree[2 * SIZE];
  10. int tree_add[2 * SIZE];
  11. int n;
  12.  
  13. void push(int v, int L, int R)
  14. {
  15.     if (L != R - 1)
  16.     {
  17.         tree_add[2 * v + 1] = tree_add[v];
  18.         tree_add[2 * v + 2] = tree_add[v];
  19.     }
  20.     tree[v] += tree_add[v] * (R - L);
  21.     tree_add[v] = 0;
  22. }
  23.  
  24. void build_sum_tree(int v, int L, int R)
  25. {
  26.     if (L == R - 1)
  27.     {
  28.         if (L < n)
  29.         {
  30.             tree[v] = a[L];
  31.         }
  32.         return;
  33.     }
  34.     int M = (L + R) / 2;
  35.     build_sum_tree(2 * v + 1, L, M);
  36.     build_sum_tree(2 * v + 2, M, R);
  37.     tree[v] = tree[2 * v + 1] + tree[2 * v + 2];
  38. }
  39.  
  40. int64_t get_summary(int v, int L, int R, int l, int r)
  41. {
  42.     push(v, L, R);
  43.     if (r <= L || R <= l) return 0;
  44.     if (l <= L && R <= r) return tree[v];
  45.     int M = (L + R) / 2;
  46.     int64_t first_child = get_summary(2 * v + 1, L, M, l, r);
  47.     int64_t second_child = get_summary(2 * v + 2, M, R, l, r);
  48.     return first_child + second_child;
  49. }
  50.  
  51. void set_in_sum_tree(int v, int L, int R, int i, int x)
  52. {
  53.     if (L == R - 1)
  54.     {
  55.         tree[v] = x;
  56.         a[i] = x;
  57.         return;
  58.     }
  59.     int M = (L + R) / 2;
  60.     if (i < M) set_in_sum_tree(2 * v + 1, L, M, i, x);
  61.     else set_in_sum_tree(2 * v + 2, M, R, i, x);
  62.     tree[v] = tree[2 * v + 1] + tree[2 * v + 2];
  63. }
  64.  
  65. void set_range(int v, int L, int R, int l, int r, int x)
  66. {
  67.     push(v, L, R);
  68.     if (r <= L || R <= l) return;
  69.     if (l <= L && R <= r)
  70.     {
  71.         tree_add[v] += x;
  72.         push(v, L, R);
  73.         return;
  74.     }
  75.     int M = (L + R) / 2;
  76.     set_range(2 * v + 1, L, M, l, r, x);
  77.     set_range(2 * v + 2, M, R, l, r, x);
  78.     tree[v] = tree[2 * v + 1] + tree[2 * v + 2];
  79. }
  80.  
  81. int main()
  82. {
  83.     int q;
  84.     cin >> n >> q;
  85.     forn (req, q)
  86.     {
  87.         char type;
  88.         cin >> type;
  89.         if (type == '1')
  90.         {
  91.             int l, r, x;
  92.             cin >> l >> r >> x;
  93.             --l;
  94.             set_range(0, 0, SIZE, l, r, x);
  95.         }
  96.         else if (type == '2')
  97.         {  
  98.             int l, r;
  99.             cin >> l >> r;
  100.             --l;
  101.             cout << get_summary(0, 0, SIZE, l, r) << endl;
  102.         }
  103.     }
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement