#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
/* Keep a lower bound and upper bound of heights in each node of
segment tree. To propagate, just get the values of the parent
node and update its lower bound and upper bound. For query, just
traverse through the segment tree for each node (point query).
*/
struct segtree {
struct Node {
int val_min, val_max;
int lazy_min; // val_min and val_max should not be lower than this
int lazy_max; // val_min and val_max should not be higher than this
Node(): val_min(0), val_max(0), lazy_min(-1), lazy_max(-1) {}
};
vector<Node> tree;
inline void lazydown(int n) {
if (tree[n].lazy_min != -1) {
tree[n * 2].val_min = max(tree[n * 2].val_min, tree[n].lazy_min);
tree[n * 2].val_max = max(tree[n * 2].val_max, tree[n].lazy_min);
tree[n * 2 + 1].val_min = max(tree[n * 2 + 1].val_min, tree[n].lazy_min);
tree[n * 2 + 1].val_max = max(tree[n * 2 + 1].val_max, tree[n].lazy_min);
}
if (tree[n].lazy_max != -1) {
tree[n * 2].val_min = min(tree[n * 2].val_min, tree[n].lazy_max);
tree[n * 2].val_max = min(tree[n * 2].val_max, tree[n].lazy_max);
tree[n * 2 + 1].val_min = min(tree[n * 2 + 1].val_min, tree[n].lazy_max);
tree[n * 2 + 1].val_max = min(tree[n * 2 + 1].val_max, tree[n].lazy_max);
}
tree[n * 2].lazy_min = tree[n * 2].val_min;
tree[n * 2].lazy_max = tree[n * 2].val_max;
tree[n * 2 + 1].lazy_min = tree[n * 2 + 1].val_min;
tree[n * 2 + 1].lazy_max = tree[n * 2 + 1].val_max;
tree[n].lazy_min = tree[n].lazy_max = -1;
}
void init(int n) {
tree.resize(4 * n + 5);
}
void update(int n, int tl, int tr, int le, int ri, int val, int type) {
if (tl > tr || tl > ri || tr < le) return;
if (le <= tl && tr <= ri) {
if (type == 1) { // add
tree[n].val_max = max(tree[n].val_max, val);
tree[n].val_min = max(tree[n].val_min, val);
tree[n].lazy_min = tree[n].val_min;
tree[n].lazy_max = tree[n].val_max;
}
if (type == 2) { // remove
tree[n].val_max = min(tree[n].val_max, val);
tree[n].val_min = min(tree[n].val_min, val);
tree[n].lazy_max = tree[n].val_max;
tree[n].lazy_min = tree[n].val_min;
}
return;
}
int mid = (tl + tr) / 2;
lazydown(n);
update(n * 2, tl, mid, le, ri, val, type);
update(n * 2 + 1, mid + 1, tr, le, ri, val, type);
tree[n].val_min = min(tree[n * 2].val_min, tree[n * 2 + 1].val_min);
tree[n].val_max = max(tree[n * 2].val_max, tree[n * 2 + 1].val_max);
}
int query(int n, int tl, int tr, int p) {
if (tl == tr) return tree[n].val_min;
int mid = (tl + tr) / 2;
lazydown(n);
if (p <= mid)
return query(n * 2, tl, mid, p);
else
return query(n * 2 + 1, mid + 1, tr, p);
}
} solver;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
solver.init(n);
for (int i = 0; i < k; i++) solver.update(1, 0, n - 1, left[i], right[i], height[i], op[i]);
for (int i = 0; i < n; i++) finalHeight[i] = solver.query(1, 0, n - 1, i);
return;
}
