#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int clamp(int x, int l, int r) {return min(r, max(l, x));}
struct SegTree {
#define m (l + (r-l)/2)
#define LEFT 2*i+1,l,m
#define RIGHT 2*i+2,m,r
#define RANGE ql, qr
int n; vector<int> low, high;
SegTree() {}
SegTree(int N) : n(N), low(4*N, -INF), high(4*N, INF) {}
void apply(int i, int x, int y) {low[i] = clamp(low[i], x, y), high[i] = clamp(high[i], x, y);}
void push_down(int i) {apply(2*i+1, low[i], high[i]), apply(2*i+2, low[i], high[i]); low[i] = -INF; high[i] = INF;}
void update(int i, int l, int r, int ql, int qr, int x, int y) { // clamps low[segment] and high[segment] to the range [x,y]
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) {apply(i, x, y); return;}
push_down(i);
update(LEFT, RANGE, x, y); update(RIGHT, RANGE, x, y);
}
int query(int i, int l, int r, int x) {
if (!(l <= x && x < r)) return 0;
if (l + 1 == r) return clamp(0, low[i], high[i]);
push_down(i);
if (x < m) return query(LEFT, x);
else return query(RIGHT, x);
}
void range_chmin(int l, int r, int x) {
update(0, 0, n, l, r+1, -INF, x);
}
void range_chmax(int l, int r, int x) {
update(0, 0, n, l, r+1, x, INF);
}
#undef m
#undef LEFT
#undef RIGHT
#undef RANGE
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
auto st = SegTree(n);
for (int i = 0; i < k; i++) {
if (op[i] == 1) st.range_chmax(left[i], right[i], height[i]);
else st.range_chmin(left[i], right[i], height[i]);
}
for (int i = 0; i < n; i++) finalHeight[i] = st.query(0, 0, n, i);
return;
}
