SHARE
TWEET

Untitled

a guest May 21st, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int64_t inf = 1000 * 1000 * 1000;
  6. int64_t inf64 = inf * inf;
  7. int64_t nll = 0;
  8.  
  9. #define ll long long
  10. #define se second
  11. #define fi first
  12. #define endl '\n'
  13.  
  14. vector <int64_t> a;
  15.  
  16. struct fruct
  17. {
  18.     int32_t l, r;
  19.     int64_t delta, val;
  20.     fruct *left, *right;
  21.     fruct(int32_t l, int32_t r, int64_t delta, int64_t val):
  22.         l(l), r(r), delta(delta),
  23.         val(val), left(0), right(0){};
  24. };
  25.  
  26. void build(fruct *cur, int32_t l, int32_t r)
  27. {
  28.     if (l == r) cur->val = a[l];
  29.     else
  30.     {
  31.         if (!cur->left) cur->left = new fruct(0, 0, 0, 0);
  32.         if (!cur->right) cur->right = new fruct(0, 0, 0, 0);
  33.         int32_t m = (l + r) / 2;
  34.         build(cur->left, l, m);
  35.         build(cur->right, m + 1, r);
  36.         cur->val = cur->left->val + cur->right->val;
  37.     }
  38.     cur->l = l;
  39.     cur->r = r;
  40.     cur->delta = 0;
  41. }
  42.  
  43. int64_t get_val(fruct *cur)
  44. {
  45.     return cur->val + cur->delta * (cur->r - cur->l + 1);
  46. }
  47.  
  48. void pull(fruct *cur)
  49. {
  50.     cur->val = get_val(cur->left) + get_val(cur->right);
  51. }
  52.  
  53. void push(fruct *cur)
  54. {
  55.     cur->left->delta += cur->delta;
  56.     cur->right->delta += cur->delta;
  57.     cur->delta = 0;
  58. }
  59.  
  60. void update(fruct *cur, int32_t l, int32_t r, int64_t d)
  61. {
  62.     if (cur->l > r || cur->r < l) return;
  63.     else if(cur->l >= l && cur->r <= r)
  64.     {
  65.         cur->delta += d;
  66.         return;
  67.     }
  68.     push(cur);
  69.     update(cur->left, l, r, d);
  70.     update(cur->right, l, r, d);
  71.     pull(cur);
  72. }
  73.  
  74. int64_t get_sum(fruct *cur, int32_t l, int32_t r)
  75. {
  76.     if (cur->l > r || cur->r < l) return 0;
  77.     else if (cur->l >= l && cur->r <= r) return get_val(cur);
  78.     push(cur);
  79.     int64_t res = get_sum(cur->left, l, r) + get_sum(cur->right, l, r);
  80.     pull(cur);
  81.     return res;
  82. }
  83.  
  84. int main() {
  85.     ios_base::sync_with_stdio(false);
  86.     cin.tie(NULL);
  87.     cout.tie(NULL);
  88.     int64_t n, q;
  89.     cin >> n >> q;
  90.     a.resize(n, 0);
  91.     fruct root(0, 0, 0, 0);
  92.     build(&root, 0, n - 1);
  93.     for (int32_t i = 0; i < q; ++i)
  94.     {
  95.         int64_t tp, l, r, x;
  96.         cin >> tp;
  97.         if (tp == 1)
  98.         {
  99.             cin >> l >> r >> x;
  100.             update(&root, l, r - 1, x);
  101.         }
  102.         else
  103.         {
  104.             cin >> l >> r;
  105.             cout << get_sum(&root, l, r - 1) << endl;
  106.         }
  107.     }
  108. }
  109. /*
  110.  
  111. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top