Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
RAW Paste Data