#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
struct Node {
int low = 0, high = INT_MAX;
};
struct Segment_Tree {
int n;
vector<Node> tree;
Segment_Tree(const int &_n) {
n = _n + 5, tree.resize(n << 2);
}
void apply(const int &v, const int &op_low, const int &op_high) {
tree[v].low = max(tree[v].low, op_low), tree[v].high = max(tree[v].high, op_low);
tree[v].low = min(tree[v].low, op_high), tree[v].high = min(tree[v].high, op_high);
}
void relax(const int &v, const int &tl, const int &tr) {
if (tl != tr)
apply(v << 1, tree[v].low, tree[v].high), apply(v << 1 | 1, tree[v].low, tree[v].high), tree[v].low = 0, tree[v].high = INT_MAX;
}
void update(const int &v, const int &tl, const int &tr, const int &l, const int &r, const int &op_low, const int &op_high) {
relax(v, tl, tr);
if (l > r || tl > r || l > tr) return;
if (l <= tl && tr <= r) {
apply(v, op_low, op_high);
relax(v, tl, tr);
return;
}
int tm = (tl + tr) >> 1;
update(v << 1, tl, tm, l, min(r, tm), op_low, op_high), update(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, op_low, op_high);
}
void build(const int &v, const int &tl, const int &tr, int res[]) {
relax(v, tl, tr);
if (tl == tr) {
res[tl] = tree[v].low;
return;
}
int tm = (tl + tr) >> 1;
build(v << 1, tl, tm, res), build(v << 1 | 1, tm + 1, tr, res);
}
};
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
Segment_Tree segtree(N);
for (int i = 0; i < K; i++) {
int L = left[i], R = right[i], H = height[i];
if (op[i] == 1) {
// adding
segtree.update(1, 0, N - 1, L, R, H, INT_MAX);
} else {
// remoing
segtree.update(1, 0, N - 1, L, R, 0, H);
}
}
segtree.build(1, 0, N - 1, finalHeight);
return;
}
