#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using Vec = vector<T>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
} else {
return false;
}
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
} else {
return false;
}
}
constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003;
i32 ceil_pow2(i32 n) {
i32 k = 1;
while (k < n) {
k *= 2;
}
return k;
}
struct Func {
i32 lo, hi;
};
Func id() {
return Func{-INF, INF};
}
Func composite(Func f, Func g) {
if (f.lo > g.hi) {
return Func{f.lo, f.lo};
}
if (f.hi < g.lo) {
return Func{f.hi, f.hi};
}
return Func{max(f.lo, g.lo), min(f.hi, g.hi)};
}
class DualSegmentTree {
i32 n;
Vec<Func> funcs;
void push(i32 idx) {
if (idx < n) {
funcs[2 * idx] = composite(funcs[idx], funcs[2 * idx]);
funcs[2 * idx + 1] = composite(funcs[idx], funcs[2 * idx + 1]);
funcs[idx] = id();
}
}
void _apply(i32 l, i32 r, Func f, i32 cur, i32 curl, i32 curr) {
if (curr <= l || r <= curl) {
return;
}
if (l <= curl && curr <= r) {
funcs[cur] = composite(f, funcs[cur]);
return;
}
i32 curm = (curl + curr) / 2;
push(cur);
_apply(l, r, f, 2 * cur, curl, curm);
_apply(l, r, f, 2 * cur + 1, curm, curr);
}
public:
DualSegmentTree(i32 n_) : n(ceil_pow2(n_)), funcs(2 * n, id()) {}
void apply(i32 l, i32 r, Func f) {
_apply(l, r, f, 1, 0, n);
}
Func get(i32 idx) const {
idx += n;
Func ret = id();
while (idx > 0) {
ret = composite(funcs[idx], ret);
idx /= 2;
}
return ret;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
DualSegmentTree seg(n);
REP(i, k) {
if (op[i] == 1) {
seg.apply(left[i], right[i] + 1, Func{height[i], INF});
} else {
seg.apply(left[i], right[i] + 1, Func{-INF, height[i]});
}
}
REP(i, n) {
Func f = seg.get(i);
finalHeight[i] = (0 < f.lo ? f.lo : 0 > f.hi ? f.hi : 0);
}
}
