#include <bits/stdc++.h>
using namespace std;
#include "wall.h"
const int INF = 1 << 30;
struct window {
int l, r;
window(int l = -INF, int r = +INF): l(l), r(r) {
assert(l <= r);
}
window operator*(const window& o) const {
window w = *this; w *= o; return w;
}
window& operator*=(const window& o) {
l = o(l); r = o(r);
return *this;
}
int operator()(int v) const {
return clamp(v, l, r);
}
};
struct Tree {
int i, j;
window v;
Tree *l, *r;
Tree(int i, int j): i(i), j(j) {
if (j - i == 1) {
v = window(0, 0);
l = r = nullptr;
} else {
int k = i + j >> 1;
l = new Tree(i, k);
r = new Tree(k, j);
}
}
void visit() {
if (l) {
l->v *= v;
r->v *= v;
v = window();
}
}
void chop(int I, int J, const window& w) {
if (I <= i && j <= J) {
v *= w;
visit();
} else {
visit();
if (!(J <= i || j <= I)) {
l->chop(I, J, w);
r->chop(I, J, w);
}
}
}
int *trav(int *t) {
visit();
if (l) {
t = l->trav(t);
t = r->trav(t);
} else {
assert(v.l == v.r);
*(t++) = v.l;
}
return t;
}
};
#define LW 1
#define HG 2
void buildWall(int n, int q, int ops[], int lfs[], int rgs[], int hts[], int finalHeight[]) {
Tree t(0, n);
for (int qq = 0; qq < q; qq++) {
t.chop(lfs[qq], ++rgs[qq], ops[qq] == LW ? window(hts[qq], INF) : window(-INF , hts[qq]));
}
t.trav(finalHeight);
}
