// GPT's code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct Node {
int mn, mx;
int s_mn, s_mx;
} st[N * 4];
int n;
Node merge(Node a, Node b) {
Node res;
res.mn = min(a.mn, b.mn);
res.mx = max(a.mx, b.mx);
// second min
if (a.mn < b.mn) res.s_mn = min(b.mn, a.s_mn);
else if (a.mn > b.mn) res.s_mn = min(a.mn, b.s_mn);
else res.s_mn = min(a.s_mn, b.s_mn);
// second max
if (a.mx > b.mx) res.s_mx = max(b.mx, a.s_mx);
else if (a.mx < b.mx) res.s_mx = max(a.mx, b.s_mx);
else res.s_mx = max(a.s_mx, b.s_mx);
return res;
}
void build(int u, int l, int r) {
if (l == r) {
st[u] = {0, 0, (int)1e9, -(int)1e9};
return;
}
int mid = (l + r) >> 1;
build(u<<1, l, mid);
build(u<<1|1, mid+1, r);
st[u] = merge(st[u<<1], st[u<<1|1]);
}
void push_chmin(int u, int x) {
if (st[u].mx <= x) return;
st[u].mx = x;
}
void push_chmax(int u, int x) {
if (st[u].mn >= x) return;
st[u].mn = x;
}
void push(int u) {
push_chmin(u<<1, st[u].mx);
push_chmin(u<<1|1, st[u].mx);
push_chmax(u<<1, st[u].mn);
push_chmax(u<<1|1, st[u].mn);
}
void pull(int u) {
st[u] = merge(st[u<<1], st[u<<1|1]);
}
void range_chmin(int u, int l, int r, int ql, int qr, int x) {
if (l > qr || r < ql || st[u].mx <= x) return;
if (ql <= l && r <= qr && st[u].s_mx < x) {
push_chmin(u, x);
return;
}
push(u);
int mid = (l + r) >> 1;
range_chmin(u<<1, l, mid, ql, qr, x);
range_chmin(u<<1|1, mid+1, r, ql, qr, x);
pull(u);
}
void range_chmax(int u, int l, int r, int ql, int qr, int x) {
if (l > qr || r < ql || st[u].mn >= x) return;
if (ql <= l && r <= qr && st[u].s_mn > x) {
push_chmax(u, x);
return;
}
push(u);
int mid = (l + r) >> 1;
range_chmax(u<<1, l, mid, ql, qr, x);
range_chmax(u<<1|1, mid+1, r, ql, qr, x);
pull(u);
}
void get(int u, int l, int r, vector<int>& res) {
if (l == r) {
res[l] = st[u].mn;
return;
}
push(u);
int mid = (l + r) >> 1;
get(u<<1, l, mid, res);
get(u<<1|1, mid+1, r, res);
}
void buildWall(int n_, int k, int op[], int left[], int right[],
int height[], int finalHeight[]) {
n = n_;
build(1, 0, n-1);
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
// add → chmax
range_chmax(1, 0, n-1, left[i], right[i], height[i]);
} else {
// remove → chmin
range_chmin(1, 0, n-1, left[i], right[i], height[i]);
}
}
vector<int> res(n);
get(1, 0, n-1, res);
for (int i = 0; i < n; i++)
finalHeight[i] = res[i];
}
