#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct SegTree {
vector<int> a, mn, mx, ls;
void push(int u) {
mn[u*2] = min(max(mn[u*2], mn[u]), mx[u]);
mx[u*2] = min(max(mx[u*2], mn[u]), mx[u]);
mn[u*2+1] = min(max(mn[u*2+1], mn[u]), mx[u]);
mx[u*2+1] = min(max(mx[u*2+1], mn[u]), mx[u]);
mn[u] = 0, mx[u] = INT_MAX;
}
void update(int u, int l, int r, int x, int y, int v, int t) {
if (x <= l && r <= y) {
if (!t) mn[u] = max(mn[u], v), mx[u] = max(mx[u], v);
else mn[u] = min(mn[u], v), mx[u] = min(mx[u], v);
return;
}
push(u);
int mid = (l + r) / 2;
if (x <= mid) update(u*2, l, mid, x, y, v, t);
if (y > mid) update(u*2+1, mid+1, r, x, y, v, t);
}
int query(int u, int l, int r, int x) {
if (l == r) return mn[u];
push(u);
int mid = (l + r) / 2;
if (x <= mid) return query(u*2, l, mid, x);
else return query(u*2+1, mid+1, r, x);
}
SegTree(int n) {
a.resize(n+1), mn.resize(4*n), mx.resize(4*n);
for (int i = 0; i < 4 * n; i++) mn[i] = 0, mx[i] = INT_MAX;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
struct SegTree T = SegTree(n);
for (int i = 0; i < k; i++) T.update(1, 1, n, left[i]+1, right[i]+1, height[i], (op[i] != 1));
for (int i = 0; i < n; i++) finalHeight[i] = T.query(1, 1, n, i+1);
}
