Advertisement
Guest User

Untitled

a guest
Dec 7th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #pragma GCC optimize("Ofast")
  4. #pragma GCC optimize("no-stack-protector")
  5. #pragma GCC optimize("unroll-loops")
  6. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  7. #define int long long
  8.  
  9. using namespace std;
  10.  
  11. const int INF = 1e9 + 7;
  12.  
  13. int n, q;
  14. vector <int> tree, add;
  15. set <pair <int, int> > all, all_inv;
  16. map <pair <int, int>, int> color;
  17.  
  18. void push(int v, int tl, int tr) {
  19. tree[v] += add[v] * (tr - tl);
  20. if (tl + 1 == tr) {
  21. add[v * 2] += add[v];
  22. add[v * 2 + 1] += add[v];
  23. }
  24. add[v] = 0;
  25. }
  26.  
  27. int get(int v, int tl, int tr, int l, int r) {
  28. push(v, tl, tr);
  29. if (tl >= r || l >= tr)
  30. return 0;
  31. else if (l <= tl && r >= tr)
  32. return tree[v];
  33. else {
  34. int tm = (tl + tr) / 2;
  35. return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm, tr, l, r);
  36. }
  37. }
  38.  
  39. void upd(int v, int tl, int tr, int l, int r, int delta) {
  40. push(v, tl, tr);
  41. if (tl >= r || l >= tr)
  42. return;
  43. else if (l <= tl && r >= tr) {
  44. add[v] += delta;
  45. push(v, tl, tr);
  46. }
  47. else {
  48. int tm = (tl + tr) / 2;
  49. upd(v * 2, tl, tm, l, r, delta);
  50. upd(v * 2 + 1, tm, tr, l, r, delta);
  51. tree[v] = tree[v * 2] + tree[v * 2 + 1];
  52. }
  53. }
  54.  
  55. int split(int mid, bool fl) {
  56. auto kek = *all_inv.lower_bound({-mid, -INF});
  57. int left = -kek.first, right = -kek.second;
  58. int c = color[{left, right}];
  59. //cout << mid << " " << fl << " " << left << " " << right << endl;
  60. if (fl) {
  61. if (mid != left) {
  62. all_inv.erase(kek);
  63. all.erase({left, right});
  64. all.insert({left, mid - 1});
  65. all_inv.insert({-left, -mid + 1});
  66. color[{left, mid - 1}] = c;
  67. color.erase(color.find({left, right}));
  68. }
  69. }
  70. else {
  71. if (mid != right) {
  72. all_inv.erase(kek);
  73. all.erase({left, right});
  74. all.insert({mid + 1, right});
  75. all_inv.insert({-mid - 1, -right});
  76. color[{mid + 1, right}] = c;
  77. color.erase(color.find({left, right}));
  78. }
  79. }
  80. return c;
  81. }
  82.  
  83. void change(int l, int r, int x) {
  84. int c1 = split(l, true);
  85. int c2 = split(r, false);
  86. auto kek = *all.lower_bound({l, -INF});
  87. upd(1, 0, n, l, kek.first, abs(c1 - x));
  88. kek = *all_inv.lower_bound({-r, -INF});
  89. int left = -kek.second;
  90. upd(1, 0, n, left + 1, r + 1, abs(c2 - x));
  91. pair <int, int> now = *all.lower_bound({l, -INF});
  92. //cout << "aaa" << endl;
  93. while (now.second <= r) {
  94. upd(1, 0, n, now.first, now.second + 1, abs(x - color[now]));
  95. all.erase(now);
  96. all_inv.erase({-now.first, -now.second});
  97. color.erase(color.find(now));
  98. if (all.lower_bound({now.second + 1, -INF}) == all.end())
  99. break;
  100. now = *all.lower_bound({now.second + 1, -INF});
  101. }
  102. all.insert({l, r});
  103. all_inv.insert({-l, -r});
  104. color[{l, r}] = x;
  105. }
  106.  
  107. int32_t main() {
  108. ios_base::sync_with_stdio(false);
  109. cin.tie(nullptr);
  110. cout.tie(nullptr);
  111. cin >> n >> q;
  112. tree.resize(4 * n);
  113. add.resize(4 * n);
  114. for (int i = 0; i < n; i++) {
  115. all.insert({i, i});
  116. all_inv.insert({-i, -i});
  117. color[{i, i}] = i;
  118. }
  119. while (q--) {
  120. /**for (auto el : all_inv) {
  121. cout << el.first << " " << el.second << endl;
  122. }
  123. cout << "\n\n";**/
  124. int type;
  125. cin >> type;
  126. if (type == 1) {
  127. int l, r, x;
  128. cin >> l >> r >> x;
  129. l--;
  130. r--;
  131. x--;
  132. change(l, r, x);
  133. }
  134. else {
  135. int l, r;
  136. cin >> l >> r;
  137. l--;
  138. cout << get(1, 0, n, l, r) << "\n";
  139. }
  140. }
  141. return 0;
  142. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement