#include <bits/stdc++.h>
using namespace std;
#include "wall.h"
const int maxh = 500'005;
struct Tag {
int lo, hi;
Tag(int _lo, int _hi) : lo(_lo), hi(_hi) {}
Tag() : lo(0), hi(maxh) {}
void apply(Tag &tag) {
int newlo = min(max(lo, tag.lo), tag.hi);
int newhi = max(min(hi, tag.hi), tag.lo);
lo = newlo;
hi = newhi;
}
};
struct Tree {
vector<Tag> tag, info;
Tree(int size) { tag.resize(size*4); info.resize(size*4); }
void pushdown(int x) {
info[x].apply(tag[x]);
if (x*2 < tag.size()) tag[x*2].apply(tag[x]);
if (x*2+1 < tag.size()) tag[x*2+1].apply(tag[x]);
tag[x] = {};
}
void update(int l, int r, int x, int xl, int xr, Tag delta) {
if (l > r) return;
pushdown(x); // order matters
if (l == xl && r == xr) {
tag[x].apply(delta);
} else {
int xm = (xl + xr) / 2;
update(l, min(r, xm), x*2, xl, xm, delta);
update(max(l, xm+1), r, x*2+1, xm+1, xr, delta);
// there is no merging
}
}
Tag query(int v, int x, int xl, int xr) {
pushdown(x);
if (xl == xr) {
return info[x];
} else {
int xm = (xl + xr) / 2;
if (v <= xm) return query(v, x*2, xl, xm);
else return query(v, x*2+1, xm+1, xr);
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
Tree tree(n);
for (int i=0; i<k; i++) {
if (op[i] == 1) {
// adding phase
tree.update(left[i], right[i], 1, 0, n-1, {height[i], maxh});
} else {
// removing phase
tree.update(left[i], right[i], 1, 0, n-1, {0, height[i]});
}
}
for (int i=0; i<n; i++) {
Tag tag = tree.query(i, 1, 0, n-1);
finalHeight[i] = tag.lo;
}
}
