Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
- #define int long long
- using namespace std;
- const int INF = 1e9 + 7;
- int n, q;
- vector <int> tree, add;
- set <pair <int, int> > all, all_inv;
- map <pair <int, int>, int> color;
- void push(int v, int tl, int tr) {
- tree[v] += add[v] * (tr - tl);
- if (tl + 1 == tr) {
- add[v * 2] += add[v];
- add[v * 2 + 1] += add[v];
- }
- add[v] = 0;
- }
- int get(int v, int tl, int tr, int l, int r) {
- push(v, tl, tr);
- if (tl >= r || l >= tr)
- return 0;
- else if (l <= tl && r >= tr)
- return tree[v];
- else {
- int tm = (tl + tr) / 2;
- return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm, tr, l, r);
- }
- }
- void upd(int v, int tl, int tr, int l, int r, int delta) {
- push(v, tl, tr);
- if (tl >= r || l >= tr)
- return;
- else if (l <= tl && r >= tr) {
- add[v] += delta;
- push(v, tl, tr);
- }
- else {
- int tm = (tl + tr) / 2;
- upd(v * 2, tl, tm, l, r, delta);
- upd(v * 2 + 1, tm, tr, l, r, delta);
- tree[v] = tree[v * 2] + tree[v * 2 + 1];
- }
- }
- int split(int mid, bool fl) {
- auto kek = *all_inv.lower_bound({-mid, -INF});
- int left = -kek.first, right = -kek.second;
- int c = color[{left, right}];
- //cout << mid << " " << fl << " " << left << " " << right << endl;
- if (fl) {
- if (mid != left) {
- all_inv.erase(kek);
- all.erase({left, right});
- all.insert({left, mid - 1});
- all_inv.insert({-left, -mid + 1});
- color[{left, mid - 1}] = c;
- color.erase(color.find({left, right}));
- }
- }
- else {
- if (mid != right) {
- all_inv.erase(kek);
- all.erase({left, right});
- all.insert({mid + 1, right});
- all_inv.insert({-mid - 1, -right});
- color[{mid + 1, right}] = c;
- color.erase(color.find({left, right}));
- }
- }
- return c;
- }
- void change(int l, int r, int x) {
- int c1 = split(l, true);
- int c2 = split(r, false);
- auto kek = *all.lower_bound({l, -INF});
- upd(1, 0, n, l, kek.first, abs(c1 - x));
- kek = *all_inv.lower_bound({-r, -INF});
- int left = -kek.second;
- upd(1, 0, n, left + 1, r + 1, abs(c2 - x));
- pair <int, int> now = *all.lower_bound({l, -INF});
- //cout << "aaa" << endl;
- while (now.second <= r) {
- upd(1, 0, n, now.first, now.second + 1, abs(x - color[now]));
- all.erase(now);
- all_inv.erase({-now.first, -now.second});
- color.erase(color.find(now));
- if (all.lower_bound({now.second + 1, -INF}) == all.end())
- break;
- now = *all.lower_bound({now.second + 1, -INF});
- }
- all.insert({l, r});
- all_inv.insert({-l, -r});
- color[{l, r}] = x;
- }
- int32_t main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- cin >> n >> q;
- tree.resize(4 * n);
- add.resize(4 * n);
- for (int i = 0; i < n; i++) {
- all.insert({i, i});
- all_inv.insert({-i, -i});
- color[{i, i}] = i;
- }
- while (q--) {
- /**for (auto el : all_inv) {
- cout << el.first << " " << el.second << endl;
- }
- cout << "\n\n";**/
- int type;
- cin >> type;
- if (type == 1) {
- int l, r, x;
- cin >> l >> r >> x;
- l--;
- r--;
- x--;
- change(l, r, x);
- }
- else {
- int l, r;
- cin >> l >> r;
- l--;
- cout << get(1, 0, n, l, r) << "\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement