#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct SGT {
int n;
vector<pair<int, int>> tree;
void init(int cn) {
tree.assign(4 * cn, {0, INT_MAX});
n = cn;
}
void comb(int i, int cmn, int cmx) {
tree[i].first = max(tree[i].first, cmn);
tree[i].second = min(tree[i].second, cmx);
if (tree[i].first > tree[i].second) {
if (tree[i].second < cmn) tree[i].second = tree[i].first;
else tree[i].first = tree[i].second;
}
}
void push(int i) {
comb(2 * i + 1, tree[i].first, tree[i].second);
comb(2 * i + 2, tree[i].first, tree[i].second);
tree[i] = {0, INT_MAX};
}
void upd(int i, int li, int ri, int l, int r, int mn, int mx) {
if (r < li or ri < l) return;
if (l <= li and ri <= r) {
comb(i, mn, mx);
return;
}
push(i);
int mid = (li + ri) / 2;
upd(2 * i + 1, li, mid, l, r, mn, mx);
upd(2 * i + 2, mid + 1, ri, l, r, mn, mx);
}
void upd(int l, int r, int mn, int mx) {
upd(0, 0, n - 1, l, r, mn, mx);
}
void apply(int i, int li, int ri) {
if (li == ri) return;
push(i);
int mid = (li + ri) / 2;
apply(2 * i + 1, li, mid);
apply(2 * i + 2, mid + 1, ri);
}
void apply() {
apply(0, 0, n - 1);
}
int find(int i, int li, int ri, int idx) {
if (li == ri) return tree[i].first;
int mid = (li + ri) / 2;
if (idx <= mid) return find(2 * i + 1, li, mid, idx);
return find(2 * i + 2, mid + 1, ri, idx);
}
int find(int i) {
return find(0, 0, n - 1, i);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SGT sgt;
sgt.init(n);
for (int i = 0; i < k; i++) {
if (op[i] == 1) sgt.upd(left[i], right[i], height[i], INT_MAX);
else sgt.upd(left[i], right[i], 0, height[i]);
}
sgt.apply();
for (int i = 0; i < n; i++) finalHeight[i] = sgt.find(i);
}
