#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
const int K = 5e5 + 5;
const int inf = 1e9;
struct {
int lb[4*N], rb[4*N], llz[4*N], rlz[4*N];
void push(int l, int r, int i){
if (l == r) return;
lb[2 * i] = max(min(lb[2 * i], rb[i]), lb[i]);
rb[2 * i] = min(max(rb[2 * i], lb[i]), rb[i]);
lb[2 * i + 1] = max(min(lb[2 * i + 1], rb[i]), lb[i]);
rb[2 * i + 1] = min(max(rb[2 * i + 1], lb[i]), rb[i]);
lb[i] = 0, rb[i] = inf;
}
void add(int l, int r, int i, int ll, int rr, int val){
push(l, r, i);
if (l >= ll && r <= rr) return lb[i] = max(lb[i], val), rb[i] = max(rb[i], val), void();
if (r < ll || l > rr) return;
int mid = (l + r) / 2;
add(l, mid, 2 * i, ll, rr, val), add(mid + 1, r, 2 * i + 1, ll, rr, val);
}
void remove(int l, int r, int i, int ll, int rr, int val){
push(l, r, i);
if (l >= ll && r <= rr) return lb[i] = min(lb[i], val), rb[i] = min(rb[i], val), void();
if (r < ll || l > rr) return;
int mid = (l + r) / 2;
remove(l, mid, 2 * i, ll, rr, val), remove(mid + 1, r, 2 * i + 1, ll, rr, val);
}
int query(int l, int r, int i, int idx){
push(l, r, i);
if (l == r) return min(lb[i], rb[i]);
int mid = (l + r) / 2;
if (idx <= mid) return query(l, mid, 2 * i, idx);
else return query(mid + 1, r, 2 * i + 1, idx);
}
} lazy;
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) lazy.add(1, n, 1, left[i] + 1, right[i] + 1, height[i]);
else lazy.remove(1, n, 1, left[i] + 1, right[i] + 1, height[i]);
}
for (int i = 0; i < n; i++) finalHeight[i] = lazy.query(1, n, 1, i + 1);
}
