#include <vector>
#include <iostream>
int clamp(int low, int high, int x) {
if (x < low) return low;
if (x > high) return high;
return x;
}
struct Req {
int min = 0;
int max = 2'000'000'000;
Req operator*(Req rhs) const {
return {
.min = clamp(min, max, rhs.min),
.max = clamp(min, max, rhs.max),
};
}
};
struct SegmentTree {
std::vector<Req> values;
int offset;
explicit SegmentTree(int o) : values(2 * o, {0, 0}), offset(o) {}
void push(int v) {
values[2 * v] = values[v] * values[2 * v];
values[2 * v + 1] = values[v] * values[2 * v + 1];
values[v] = Req{};
}
void update(int l, int r, Req upd) { update(l, r, upd, 1, 0, offset); }
void update(int l, int r, Req upd, int v, int s, int e) {
if (e <= l || r <= s) {
return;
} else if (l <= s && e <= r) {
values[v] = upd * values[v];
} else {
int m = (s + e) / 2;
push(v);
update(l, r, upd, 2 * v, s, m);
update(l, r, upd, 2 * v + 1, m, e);
values[v] = Req{};
}
}
void canonicalise() {
for (int i = 1; i < offset; i++) push(i);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
int finalHeight[]) {
int o = 1;
while (o < n) o *= 2;
SegmentTree st(o);
for (int i = 0; i < k; i++) {
int l = left[i];
int r = right[i] + 1;
Req upd;
if (op[i] == 1) upd.min = height[i];
if (op[i] == 2) upd.max = height[i];
st.update(l, r, upd);
}
st.canonicalise();
for (int i = 0; i < n; i++) finalHeight[i] = st.values[i + o].min;
}
