Advertisement
Guest User

Untitled

a guest
Oct 21st, 2018
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector <long long> tree;
  6.  
  7. void push(int x){
  8.     tree[x * 2 + 1] += tree[x];
  9.     tree[x * 2 + 2] += tree[x];
  10.     tree[x] = 0;
  11. }
  12.  
  13. void upd(int id, int l, int r, int ll, int rr, int s)
  14. {
  15.  
  16.     if (rr <= l || ll  >= r){
  17.         return;
  18.     }
  19.  
  20.     if (r <= rr && l >= ll){
  21.         cout << l << ' ' << r << endl;
  22.         tree[id] += s;
  23.         tree[id] = (tree[id] < 0 ? 0 : tree[id]);
  24.         return;
  25.     }
  26.  
  27.     push(id);
  28.  
  29.     int m = (l + r) / 2;
  30.     upd(id * 2 + 1, l, m, ll, rr, s);
  31.     upd(id * 2 + 2, m, r, ll, rr, s);
  32.     return;
  33. }
  34.  
  35.  
  36. int fun(int id, int l, int r, int ll, int rr)
  37. {
  38.     if (rr <= l || ll  >= r){
  39.         return 0;
  40.     }
  41.  
  42.     if (r <= rr && l >= ll){
  43.         return tree[id] * (r - l);
  44.     }
  45.  
  46.     push(id);
  47.  
  48.     int m = (l + r) / 2;
  49.     return fun(id * 2 + 1, l, m, ll, rr) + fun(id * 2 + 2, m, r, ll, rr);
  50. }
  51.  
  52.  
  53.  
  54. int main()
  55. {
  56.     /*ios_base::sync_with_stdio(false);
  57.     cin.tie(NULL);
  58.     cout.tie(NULL);*/
  59.  
  60.     int n,m;
  61.     cin >> n >> m;
  62.     n++;
  63.     tree.resize(4*n, 0);
  64.  
  65.     for (int i = 0; i < m; ++i){
  66.         int a;
  67.         cin >> a;
  68.         if (a == 1){
  69.             int l, r, s;
  70.             cin >> l >> r >> s;
  71.             r++;
  72.             upd(0, 0, n, l, r, s);
  73.             cout << "__________";
  74.         } else {
  75.             int l, r;
  76.             cin >> l >> r;
  77.             r++;
  78.             cout << fun(0, 0, n, l, r) << '\n';
  79.         }
  80.     }
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement