Advertisement
dan_sml

Untitled

Jul 16th, 2020
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 1e4 + 7, NEUTRAL = 0;
  6. int t[4 * maxn], c[4 * maxn];
  7.  
  8. void push(int v) {
  9.     c[2 * v + 1] += c[v];
  10.     c[2 * v + 2] += c[v];
  11.     c[v] = 0;
  12.     return;
  13. }
  14.  
  15. void update(int v, int l, int m, int r) {
  16.     t[v] = t[2 * v + 1] + c[2 * v + 1] * (m - l) +
  17.            t[2 * v + 2] + c[2 * v + 2] * (r - m);
  18.     return;
  19. }
  20.  
  21. void change(int v, int l, int r, int askl, int askr, int val) {
  22.     if (askr <= l || r <= askl) {
  23.         return;
  24.     }
  25.     if (askl <= l && r <= askr) {
  26.         c[v] += val;
  27.         return;
  28.     }
  29.     push(v);
  30.     int m = (r + l) / 2;
  31.     change(2 * v + 1, l, m, askl, askr, val);
  32.     change(2 * v + 2, m, r, askl, askr, val);
  33.     update(v, l, m, r);
  34.     return;
  35. }
  36.  
  37. int ask(int v, int l, int r, int askl, int askr) {
  38.     if (askr <= l || r <= askl) {
  39.         return NEUTRAL;
  40.     }
  41.     if (askl <= l && r <= askr) {
  42.         return t[v] + c[v] * (r - l);
  43.     }
  44.     push(v);
  45.     int m = (r + l) / 2;
  46.     int ans = ask(2 * v + 1, l, m, askl, askr) + ask(2 * v + 2, m, r, askl, askr);
  47.     update(v, l, m, r);
  48.     return ans;
  49. }
  50.  
  51. signed main() {
  52.     ios::sync_with_stdio(0);
  53.     cin.tie(0);
  54.     int n, m;
  55.     cin >> n >> m;
  56.     for (int i = 0; i < m; i++) {
  57.         int type, l, r, s;
  58.         cin >> type;
  59.         if (type == 1) {
  60.             cin >> l >> r >> s;
  61.             change(0, 0, n, l, r, s);
  62.         }
  63.         else {
  64.             cin >> l >> r;
  65.             cout << ask(0, 0, n, l, r) << "\n";
  66.         }
  67.     }
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement