#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct treap {
treap *l = nullptr, *r = nullptr;
int x, y, p;
int c;
int lazy = 0;
int val;
void pushdown() {
if (l != nullptr) l -> lazy += lazy;
if (r != nullptr) r -> lazy += lazy;
val += lazy;
c += lazy;
lazy = 0;
}
void upd() {
pushdown();
if (l != nullptr) l -> pushdown();
if (r != nullptr) r -> pushdown();
siz = ((l == nullptr) ? 0 : l -> siz) + ((r == nullptr) ? 0 : r -> siz) + 1;
val = max(c, max((l == nullptr) ? c : l -> val, (r == nullptr) ? c : r -> val));
}
treap(int a, int pp, int cc) : x(a), y(rng()), p(pp), c(cc) {val = c;}
};
int siz(treap *t) { return (t == nullptr) ? 0 : t -> siz; }
treap* merge(treap *t1, treap *t2) {
if (t1 == nullptr)
return t2;
if (t2 == nullptr)
return t1;
t1 -> pushdown();
t2 -> pushdown();
if (t1 -> y > t2 -> y) {
t1 -> r = merge(t1 -> r, t2);
t1 -> upd();
return t1;
} else {
t2 -> l = merge(t1, t2 -> l);
t2 -> upd();
return t2;
}
}
pair<treap*, treap*> split(treap *t, int x, int pos) {
if (t == nullptr)
return {nullptr, nullptr};
t -> pushdown();
if (t -> x > x || (t -> x == x && t -> p >= pos)) {
auto tmp = split(t -> l, x, pos);
t -> l = tmp.second;
t -> upd();
return {tmp.first, t};
} else {
auto tmp = split(t -> r, x, pos);
t -> r = tmp.first;
t -> upd();
return {t, tmp.second};
}
}
inline void addAll(treap *t, int a) { if (t != nullptr) t -> lazy += a; }
treap *root;
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
int n = A.size();
pair<int, int> B[n];
for (int i = 0; i < n; i++)
B[i] = {A[i], i};
sort(B, B + n);
for (int i = 0; i < n; i++)
root = merge(root, new treap(B[i].fs, B[i].sc, B[i].sc - i));
vector<int> answer(X.size());
for (unsigned int query = 0; query < X.size(); query++) {
int pos = X[query], val = V[query];
if (A[pos] > val) {
//a.fs -end position of element- b.fs -this element- th.sc
auto a = split(root, val, pos);
auto b = split(a.sc, A[pos], pos);
auto th = split(b.sc, A[pos], pos + 1);
addAll(b.fs, -1);
treap *d = new treap(val, pos, pos - siz(a.fs));
root = merge(merge(a.fs, d), merge(b.fs, th.sc));
} else {
//a.fs -this element- b.fs -end position of element- b.sc
auto a = split(root, A[pos], pos);
auto th = split(a.sc, A[pos], pos + 1);
auto b = split(th.sc, val, pos);
addAll(b.fs, 1);
treap *d = new treap(val, pos, pos - siz(a.fs) - siz(b.fs));
root = merge(merge(a.fs, b.fs), merge(d, b.sc));
}
A[pos] = val;
root -> pushdown();
answer[query] = root -> val;
}
return answer;
}
Compilation message
bubblesort2.cpp: In member function 'void treap::upd()':
bubblesort2.cpp:27:3: error: 'siz' was not declared in this scope
siz = ((l == nullptr) ? 0 : l -> siz) + ((r == nullptr) ? 0 : r -> siz) + 1;
^~~
bubblesort2.cpp:27:3: note: suggested alternative: 'sin'
siz = ((l == nullptr) ? 0 : l -> siz) + ((r == nullptr) ? 0 : r -> siz) + 1;
^~~
sin
bubblesort2.cpp:27:36: error: 'struct treap' has no member named 'siz'
siz = ((l == nullptr) ? 0 : l -> siz) + ((r == nullptr) ? 0 : r -> siz) + 1;
^~~
bubblesort2.cpp:27:70: error: 'struct treap' has no member named 'siz'
siz = ((l == nullptr) ? 0 : l -> siz) + ((r == nullptr) ? 0 : r -> siz) + 1;
^~~
bubblesort2.cpp: In function 'int siz(treap*)':
bubblesort2.cpp:34:54: error: 'struct treap' has no member named 'siz'
int siz(treap *t) { return (t == nullptr) ? 0 : t -> siz; }
^~~
