#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
const int inf = 2e9;
vector<int> mn, mx;
int sz;
// first mx, then mn
void impact(int x, int op, int v) {
if (op == 1) {
mx[x] = max(mx[x], v);
if (mn[x] < v) {
if (2 * x + 2 < mn.size()) {
impact(2 * x + 1, 2, mn[x]);
impact(2 * x + 2, 2, mn[x]);
}
mn[x] = inf;
}
} else {
mn[x] = min(mn[x], v);
if (mx[x] >= mn[x]) {
mx[x] = mn[x];
}
}
}
void propagate(int x) {
if (mx[x] != 0) {
impact(2 * x + 1, 1, mx[x]);
impact(2 * x + 2, 1, mx[x]);
mx[x] = 0;
}
if (mn[x] != inf) {
impact(2 * x + 1, 2, mn[x]);
impact(2 * x + 2, 2, mn[x]);
mn[x] = inf;
}
}
void upd(int l, int r, int op, int v, int x, int lx, int rx) {
if (l >= rx or lx >= r) return;
if (l <= lx and rx <= r) {
impact(x, op, v);
return;
}
propagate(x);
int mid = (lx + rx) >> 1;
upd(l, r, op, v, 2 * x + 1, lx, mid);
upd(l, r, op, v, 2 * x + 2, mid, rx);
}
int get(int i, int x, int lx, int rx) {
// cout << lx << ' ' << rx << ' ' << mx[x] << ' ' << mn[x] << endl;
if (rx - lx == 1) {
return min(mx[x], mn[x]);
}
propagate(x);
int mid = (lx + rx) >> 1;
if (i < mid) return get(i, 2 * x + 1, lx, mid);
return get(i, 2 * x + 2, mid, rx);
}
void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[]) {
sz = 1;
while (sz < n) sz *= 2;
mn.assign(2 * sz - 1, inf); mx.assign(2 * sz - 1, 0);
vector<int> brute_ans(n);
for (int i = 0; i < q; i++) {
upd(left[i], right[i] + 1, op[i], height[i], 0, 0, sz);
#ifdef sunnatov
for (int j = left[i]; j <= right[i]; j++) {
if (op[i] == 1) brute_ans[j] = max(brute_ans[j], height[i]);
else brute_ans[j] = min(brute_ans[j], height[i]);
}
// for (int j = 0; j < n; j++) {
// finalHeight[j] = get(j, 0, 0, sz);
// if (finalHeight[j] != brute_ans[j]) {
// cout << j << ' ' << brute_ans[j] << ' ' << finalHeight[j] << endl;
// }
// assert(finalHeight[j] == brute_ans[j]);
// }
#endif
}
for (int i = 0; i < n; i++) {
finalHeight[i] = get(i, 0, 0, sz);
#ifdef sunnatov
if (finalHeight[i] != brute_ans[i]) {
cout << i << ' ' << brute_ans[i] << ' ' << finalHeight[i] << endl;
}
assert(finalHeight[i] == brute_ans[i]);
#endif
}
}
