Advertisement
Guest User

Untitled

a guest
May 21st, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.33 KB | None | 0 0
  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. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement