#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = long long;
struct SegmentTree {
int n;
vector<int> arr, treeMin, treeMax; // lower bound on value, upper bound on value
void build(int i, int l, int r) {
if (l + 1 == r) {
treeMin[i] = treeMax[i] = arr[l];
return;
}
int m = l + (r - l) / 2;
build(2 * i + 1, l, m);
build(2 * i + 2, m, r);
treeMin[i] = max(treeMin[2*i+1], treeMin[2*i+2]);
treeMax[i] = min(treeMax[2*i+1], treeMax[2*i+2]);
}
void apply_update(int i, int minV, int maxV) {
treeMin[i] = max(treeMin[i], minV);
treeMax[i] = max(treeMax[i], treeMin[i]);
treeMax[i] = min(treeMax[i], maxV);
treeMin[i] = min(treeMin[i], treeMax[i]);
}
void push_down(int i) {
apply_update(2 * i + 1, treeMin[i], treeMax[i]);
apply_update(2 * i + 2, treeMin[i], treeMax[i]);
treeMin[i] = 0;
treeMax[i] = INT_MAX;
}
int query(int i, int l, int r, int idx) {
if (l + 1 == r) return treeMin[i];
push_down(i);
int m = l + (r - l) / 2;
return (idx < m) ? query(2*i+1, l, m, idx) : query(2*i+2, m, r, idx);
}
void update(int i, int l, int r, int uL, int uR, int uMin, int uMax) {
if (r <= uL || uR <= l) return;
if (uL <= l && r <= uR) {
apply_update(i, uMin, uMax);
return;
}
push_down(i);
int m = l + (r - l) / 2;
update(2 * i + 1, l, m, uL, uR, uMin, uMax);
update(2 * i + 2, m, r, uL, uR, uMin, uMax);
}
SegmentTree(int n) {
this->n = n;
this->treeMin.assign(4 * n, 0);
this->treeMax.assign(4 * n, INT_MAX);
// build(0, 0, n);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
auto st = SegmentTree(n);
for (int i = 0; i < k; i++) {
if (op[i] == 1) { // add
st.update(0, 0, n, left[i], right[i]+1, height[i], INT_MAX);
} else if (op[i] == 2) {
st.update(0, 0, n, left[i], right[i]+1, 0, height[i]);
}
}
for (int i = 0; i < n; i++) {
// finalHeight[i] = query_sum(i, i);
finalHeight[i] = st.query(0, 0, n, i);
}
return;
}
