#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct SegTree {
int size = 1;
vector<int> mx, mn;
SegTree(int n) {
while (size < n) size <<= 1;
mx.resize(2*size, 0); mn.resize(2*size, 0);
}
void modify_op(int x, int t, int v) {
if (t == 1) {
mn[x] = max(mn[x], v);
mx[x] = max(mx[x], v);
} else if (t == 2) {
mn[x] = min(mn[x], v);
mx[x] = min(mx[x], v);
}
}
void propagate(int x, int lx, int rx) {
if (rx - lx == 1) return;
modify_op(2*x+1, 1, mn[x]);
modify_op(2*x+2, 1, mn[x]);
modify_op(2*x+1, 2, mx[x]);
modify_op(2*x+2, 2, mx[x]);
}
void modify(int l, int r, int t, int v, int x, int lx, int rx) {
propagate(x, lx, rx);
if (r <= lx || rx <= l) return;
if (l <= lx && rx <= r) return modify_op(x, t, v);
int m = (lx + rx) >> 1;
modify(l, r, t, v, 2*x+1, lx, m); modify(l, r, t, v, 2*x+2, m, rx);
mx[x] = max(mx[2*x+1], mx[2*x+2]);
mn[x] = min(mn[2*x+1], mn[2*x+2]);
}
void modify(int l, int r, int t, int v) { modify(l, r, t, v, 0, 0, size); }
void calc(vector<int> &a, int x, int lx, int rx) {
propagate(x, lx, rx);
if (rx - lx == 1) {
if (lx < a.size()) a[lx] = mn[x];
return;
}
int m = (lx + rx) >> 1;
calc(a, 2*x+1, lx, m); calc(a, 2*x+2, m, rx);
}
void calc(vector<int> &a) { return calc(a, 0, 0, size); }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SegTree st(n);
for (int i = 0; i < k; i++) {
st.modify(left[i], right[i]+1, op[i], height[i]);
}
vector<int> a(n); st.calc(a);
for (int i = 0; i < n; i++) finalHeight[i] = a[i];
return;
}
