#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) {
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) {
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, inf); mx.assign(2 * sz, 0);
for (int i = 0; i < q; i++) {
upd(left[i], right[i] + 1, op[i], height[i], 0, 0, sz);
}
for (int i = 0; i < n; i++) {
finalHeight[i] = get(i, 0, 0, sz);
}
}
