Untitled

#include <bits/stdc++.h>
#define int long long

using namespace std;

mt19937 rnd(time(nullptr));

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 (l >= tr || tl >= r)
        return 0;
    else if (l <= tl && r >= tr)
        return tree[v];
    else {
        int tm = (tl + tr) / 2;
        auto kek = get(v * 2, tl, tm, l, r);
        auto lol = get(v * 2 + 1, tm, tr, l, r);
        return kek + lol;
    }
}

void upd(int v, int tl, int tr, int l, int r, int delta) {
    push(v, tl, tr);
    if (l >= tr || tl >= r)
        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}];
    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) {
    auto lol = *all_inv.lower_bound({-l, -INF});
    if (-lol.first <= l && r <= -lol.second) {
        pair <int, int> kek = {-lol.first, -lol.second};
        all.erase(kek);
        all_inv.erase(lol);
        int c = color[kek];
        color.erase(kek);
        if (kek.first != l - 1) {
            all.insert({kek.first, l - 1});
            all_inv.insert({-kek.first, -l + 1});
            color[{kek.first, l - 1}] = c;
        }
        if (r != kek.second) {
            all.insert({r + 1, kek.second});
            all_inv.insert({-r - 1, -kek.second});
            color[{r + 1, kek.second}] = c;
        }
        all.insert({l, r});
        all_inv.insert({-l, -r});
        color[{l, r}] = x;
        upd(1, 0, n, l, r + 1, abs(x - c));
        return;
    }
    //cout << "aa" << endl;
    int c1 = split(l, true);
    int c2 = split(r, false);
    auto kek = *all.lower_bound({l, -INF});
    if (kek.first != l)
        upd(1, 0, n, l, kek.first, abs(c1 - x));
    kek = *all_inv.lower_bound({-r, -INF});
    int left = -kek.second;
    if (left != r)
        upd(1, 0, n, left + 1, r + 1, abs(c2 - x));
    pair <int, int> now = {INF, INF};
    if (all.lower_bound({l, -INF}) != all.end())
        now = *all.lower_bound({l, -INF});
    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, -INF}) == all.end())
            break;
        now = *all.lower_bound({now.second, -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);
    while (true) {
        //cin >> n >> q;
        n = rnd() % 6 + 1, q = rnd() % 6 + 1;
        tree.resize(4 * n);
        add.resize(4 * n);
        vector <int> num(n), smth(n);
        for (int i = 0; i < n; i++) {
            all.insert({i, i});
            all_inv.insert({-i, -i});
            color[{i, i}] = i;
            num[i] = i;
        }
        vector <int> ans1, ans2;
        vector <vector <int> > queries;
        while (q--) {
            int type;
            //cin >> type;
            type = rnd() % 2 + 1;
            if (type == 1) {
                int l, r, x;
                //cin >> l >> r >> x;
                l = rnd() % n + 1, r = rnd() % n + 1, x = rnd() % 7 + 1;
                if (l > r)
                    swap(l, r);
                l--;
                r--;
                x--;
                change(l, r, x);
                for (int i = l; i <= r; i++) {
                    smth[i] += abs(x - num[i]);
                    num[i] = x;
                }
                queries.push_back({1, l + 1, r + 1, x});
            }
            else {
                int l, r;
                //cin >> l >> r;
                l = rnd() % n + 1, r = rnd() % n + 1;
                if (l > r)
                    swap(l, r);
                l--;
                ans1.push_back(get(1, 0, n, l, r));
                int res = 0;
                for (int i = l; i < r; i++)
                    res += smth[i];
                ans2.push_back(res);
                queries.push_back({2, l + 1, r + 1});
            }
        }
        for (int i = 0; i < (int)ans1.size(); i++) {
            if (ans1[i] != ans2[i]) {
                cout << n << " " << (int)queries.size() << "\n";
                for (auto el : queries) {
                    for (auto elem : el)
                        cout << elem << " ";
                    cout << "\n";
                }
                return 0;
            }
        }
        cout << "OK" << endl;
    }
    return 0;
}