Advertisement
ke_timofeeva7

Untitled

Oct 30th, 2021
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.26 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <sstream>
  4. #include <vector>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <memory.h>
  8. #include <stdio.h>
  9. #include <stack>
  10. #include <deque>
  11. #include <queue>
  12. #include <set>
  13. #include <iterator>
  14. #include <map>
  15. #include <iomanip>
  16. #include <unordered_set>
  17. #define int long long
  18. #define pb push_back
  19. #define double long double
  20. #define endl "\n"
  21. #define fir first
  22. #define sec second
  23. #define un unsigned
  24. #define INF 1000000007
  25. #define pii pair<int, int>
  26. #define all(v) v.begin(), v.end()
  27. using namespace std;
  28.  
  29. const int N = 1000000, R = 1 << 19;
  30. const int MOD = 1e9 + 7;
  31.  
  32. vector<int> tree;
  33. vector<int> flag;
  34.  
  35. void push(int v, int size)
  36. {
  37. for (int i = 0; i < 2; i++)
  38. {
  39. tree[v * 2 + i] += flag[v] * size / 2;
  40. flag[v * 2 + i] += flag[v];
  41. }
  42.  
  43. flag[v] = 0;
  44. return;
  45. }
  46.  
  47. void modify(int ql, int qr, int v, int nl, int nr, int add)
  48. {
  49. if (nr < ql || nl > qr)
  50. {
  51. return;
  52. }
  53.  
  54. if (nl >= ql && nr <= qr)
  55. {
  56. tree[v] += add * (nr - nl + 1);
  57. flag[v] += add;
  58. return;
  59. }
  60.  
  61. push(v, nr - nl + 1);
  62.  
  63. int nm = (nl + nr) / 2;
  64.  
  65. modify(ql, qr, 2 * v, nl, nm, add);
  66. modify(ql, qr, 2 * v + 1, nm + 1, nr, add);
  67.  
  68. tree[v] = tree[2 * v] + tree[2 * v + 1];
  69. return;
  70. }
  71.  
  72. int sum(int ql, int qr, int v, int nl, int nr)
  73. {
  74. if (nl > qr || nr < ql)
  75. {
  76. return 0;
  77. }
  78.  
  79. if (nl >= ql && nr <= qr)
  80. {
  81. return tree[v];
  82. }
  83.  
  84. push(v, nr - nl + 1);
  85.  
  86. int nm = (nl + nr) / 2;
  87.  
  88. int lol = sum(ql, qr, 2 * v, nl, nm);
  89. int kek = sum(ql, qr, 2 * v + 1, nm + 1, nr);
  90.  
  91. return lol + kek;
  92. }
  93.  
  94. signed main()
  95. {
  96. ios_base::sync_with_stdio(false);
  97. cin.tie(0);
  98. cout.tie(0);
  99.  
  100. int n, m;
  101. cin >> n >> m;
  102.  
  103. tree.resize(2 * R + 5, 0);
  104. flag.resize(2 * R + 5, 0);
  105.  
  106. for (int i = 0; i < m; i++)
  107. {
  108. int type;
  109. cin >> type;
  110.  
  111. if (type == 1)
  112. {
  113. int l, r, x;
  114. cin >> l >> r >> x;
  115.  
  116. modify(l, r, 1, 1, R, x);
  117. }
  118. else
  119. {
  120. int l, r;
  121. cin >> l >> r;
  122.  
  123. cout << sum(l, r, 1, 1, R) << endl;
  124. }
  125. }
  126.  
  127. return 0;
  128. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement