Advertisement
dan_sml

Untitled

Jul 16th, 2020
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.48 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.     int m = (r + l) / 2;
  30.     change(2 * v + 1, l, m, askl, askr, val);
  31.     change(2 * v + 2, m, r, askl, askr, val);
  32.     update(v, l, m, r);
  33.     return;
  34. }
  35.  
  36. int ask(int v, int l, int r, int askl, int askr) {
  37.     if (askr <= l || r <= askl) {
  38.         return NEUTRAL;
  39.     }
  40.     if (askl <= l && r <= askr) {
  41.         return t[v] + c[v] * (r - l);
  42.     }
  43.     push(v);
  44.     int m = (r + l) / 2;
  45.     update(v, l, m, r);
  46.     return ask(2 * v + 1, l, m, askl, askr) + ask(2 * v + 2, m, r, askl, askr);
  47. }
  48.  
  49. signed main() {
  50.     ios::sync_with_stdio(0);
  51.     cin.tie(0);
  52.     int n, m;
  53.     cin >> n >> m;
  54.     for (int i = 0; i < m; i++) {
  55.         int type, l, r, s;
  56.         cin >> type;
  57.         if (type == 1) {
  58.             cin >> l >> r >> s;
  59.             change(0, 0, n, l, r, s);
  60.         }
  61.         else {
  62.             cin >> l >> r;
  63.             cout << ask(0, 0, n, l, r) << "\n";
  64.         }
  65.     }
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement