SHARE
TWEET

Untitled

a guest Dec 7th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
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