#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 21);
const int INF = 1e9;
int tr_min[2 * N];
int tr_max[2 * N];
void setpush(int v, int l, int r) {
tr_min[v] = max(tr_min[v], l);
tr_min[v] = min(tr_min[v], r);
tr_max[v] = max(tr_max[v], l);
tr_max[v] = min(tr_max[v], r);
}
void push(int v) {
if (v >= N) return;
setpush(2 * v, tr_min[v], tr_max[v]);
setpush(2 * v + 1, tr_min[v], tr_max[v]);
}
void update(int ql, int qr, int lb, int rb, int l = 0, int r = N - 1, int v = 1) {
if (r < ql || l > qr)
return;
if (ql <= l && r <= qr) {
setpush(v, lb, rb);
return;
}
push(v);
int mid = (l + r) / 2;
update(ql, qr, lb, rb, l, mid, 2 * v);
update(ql, qr, lb, rb, mid + 1, r, 2 * v + 1);
tr_min[v] = min(tr_min[2 * v], tr_min[2 * v + 1]);
tr_max[v] = max(tr_max[2 * v], tr_max[2 * v + 1]);
}
int arr[N];
void construct(int l = 0, int r = N - 1, int v = 1) {
if (l == r) {
arr[l] = tr_min[v];
return;
}
push(v);
int mid = (l + r) / 2;
construct(l, mid, 2 * v);
construct(mid + 1, r, 2 * v + 1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
update(left[i], right[i], height[i], INF);
} else {
update(left[i], right[i], 0, height[i]);
}
}
construct();
for (int i = 0; i < n; i++)
finalHeight[i] = arr[i];
return;
}
