Advertisement
Guest User

Untitled

a guest
Oct 15th, 2018
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.36 KB | None | 0 0
  1. #include <iostream>
  2. #include <ctime>
  3. #include <iomanip>
  4. #include <vector>
  5. #include <map>
  6. #include <algorithm>
  7. #include <string>
  8. #include <cmath>
  9. #include <set>
  10. #include <unordered_set>
  11. #include <unordered_map>
  12. #include <chrono>
  13. #include <stack>
  14. #include <cassert>
  15. #include <queue>
  16. #include <deque>
  17. #include <climits>
  18. #include <cstring>
  19. #include <random>
  20. #include <bitset>
  21.  
  22. using namespace std;
  23.  
  24.  
  25. struct segment_tree {
  26. private:
  27.  
  28. typedef long long ll;
  29. const ll inf = 1e18;
  30.  
  31. int size;
  32. vector<ll> t;
  33. vector<ll> mod_add;
  34. vector<ll> mod_set;
  35.  
  36. void pull(int v) {
  37. t[v] = t[2 * v + 1] + t[2 * v + 2];
  38. }
  39.  
  40. void update_set(int v, int l, int r, ll val) {
  41. t[v] = (ll)(r - l) * val;
  42. mod_set[v] = val;
  43. mod_add[v] = -inf;
  44. }
  45.  
  46. void update_add(int v, int l, int r, ll val) {
  47. t[v] += (ll)(r - l) * val;
  48. if (mod_add[v] == -inf) {
  49. mod_add[v] = val;
  50. } else {
  51. mod_add[v] += val;
  52. }
  53. }
  54.  
  55. void push(int v, int l, int r) {
  56. if (mod_set[v] != -inf) {
  57. int m = (r + l) >> 1;
  58. update_set(2 * v + 1, l, m, mod_set[v]);
  59. update_set(2 * v + 2, m, r, mod_set[v]);
  60. } else if (mod_add[v] != -inf) {
  61. int m = (r + l) >> 1;
  62. update_add(2 * v + 1, l, m, mod_add[v]);
  63. update_add(2 * v + 2, m, r, mod_add[v]);
  64. mod_add[v] = -inf;
  65. }
  66. }
  67.  
  68. void build(int v, int l, int r, const vector<int> &a) {
  69. mod_add[v] = -inf;
  70. mod_set[v] = -inf;
  71. if (l + 1 == r) {
  72. t[v] = a[l];
  73. } else {
  74. int m = (r + l) >> 1;
  75. build(2 * v + 1, l, m, a);
  76. build(2 * v + 2, m, r, a);
  77. pull(v);
  78. }
  79. }
  80.  
  81. void query_add(int v, int l, int r, int ql, int qr, ll val) {
  82. if (qr <= l || r <= ql) {
  83. return;
  84. } else if (ql <= l && r <= qr) {
  85. update_add(v, l, r, val);
  86. } else {
  87. push(v, l, r);
  88. int m = (r + l) >> 1;
  89. query_add(2 * v + 1, l, m, ql, qr, val);
  90. query_add(2 * v + 2, m, r, ql, qr, val);
  91. pull(v);
  92. }
  93. }
  94.  
  95. void query_set(int v, int l, int r, int ql, int qr, ll val) {
  96. cerr << l << ' ' << r << '\n';
  97. if (qr <= l || r <= ql) {
  98. return;
  99. } else if (ql <= l && r <= qr) {
  100. cerr << "UU PITUH \n";
  101. cerr << l << ' ' << r << ' ';
  102. update_set(v, l, r, val);
  103. cerr << t[v] << '\n';
  104. } else {
  105. push(v, l, r);
  106. int m = (r + l) >> 1;
  107. query_set(2 * v + 1, l, m, ql, qr, val);
  108. query_set(2 * v + 2, m, r, ql, qr, val);
  109. pull(v);
  110. }
  111. }
  112.  
  113. ll query_sum(int v, int l, int r, int ql, int qr) {
  114. if (qr <= l || r <= ql) {
  115. return 0;
  116. } else if (ql <= l && r <= qr) {
  117. return t[v];
  118. } else {
  119. push(v, l, r);
  120. int m = (r + l) >> 1;
  121. auto f = query_sum(2 * v + 1, l, m, ql, qr);
  122. auto s = query_sum(2 * v + 2, m, r, ql, qr);
  123. pull(v);
  124. return f + s;
  125. }
  126. }
  127.  
  128. public:
  129. segment_tree(const vector<int> &a) {
  130. size = (int)a.size();
  131. t.resize(4 * size);
  132. mod_add.resize(4 * size);
  133. mod_set.resize(4 * size);
  134. build(0, 0, size, a);
  135. }
  136.  
  137. void add(int l, int r, int val) {
  138. query_add(0, 0, size, l, r, (ll)val);
  139. }
  140.  
  141. void set(int l, int r, int val) {
  142.  
  143. query_set(0, 0, size, l, r, (ll)val);
  144. }
  145.  
  146. ll sum(int l, int r) {
  147. return query_sum(0, 0, size, l, r);
  148. }
  149. };
  150.  
  151. struct arrayy {
  152. typedef long long ll;
  153. vector<ll> a;
  154.  
  155. arrayy(const vector<int> &uu) {
  156. for (auto t : uu) {
  157. a.push_back(t);
  158. }
  159. }
  160.  
  161. void add(int l, int r, int val) {
  162. for (int i = l; i < r; i++) {
  163. a[i] += val;
  164. }
  165. }
  166.  
  167. void set(int l, int r, int val) {
  168. for (int i = l; i < r; i++) {
  169. a[i] = val;
  170. }
  171. }
  172.  
  173.  
  174. ll sum(int l, int r) {
  175. ll res = 0;
  176. for (int i = l; i < r; i++) {
  177. res += a[i];
  178. }
  179. return res;
  180. }
  181. };
  182.  
  183. signed main() {
  184. ios_base::sync_with_stdio(false);
  185. cin.tie(nullptr);
  186.  
  187. #ifdef LOCAL
  188. assert(freopen("input.txt", "r", stdin));
  189. assert(freopen("output.txt", "w", stdout));
  190. #endif
  191.  
  192.  
  193. int n;
  194. cin >> n;
  195. vector<int> a(n);
  196. for (auto &t : a) {
  197. cin >> t;
  198. }
  199. arrayy cur(a);
  200. int q;
  201. cin >> q;
  202. while (q--) {
  203. int tp;
  204. cin >> tp;
  205. if (tp == 1) {
  206. //add
  207. int l, r, val;
  208. cin >> l >> r >> val;
  209. l--;
  210. cur.add(l, r, val);
  211. } else if (tp == 2) {
  212. //set
  213. int l, r, val;
  214. cin >> l >> r >> val;
  215. l--;
  216. cur.set(l, r, val);
  217. } else if (tp == 3) {
  218. //sum
  219. int l, r;
  220. cin >> l >> r;
  221. l--;
  222. auto res = cur.sum(l, r);
  223. cout << res << '\n';
  224. } else {
  225. assert(0);
  226. }
  227. }
  228. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement