#include "wall.h"
#include <bits/stdc++.h>
template <typename T, typename L, typename F = std::plus<T>>
struct SegmentTree {
int n;
std::vector<T> tree;
std::vector<L> lazy;
SegmentTree(int _n) : n(_n), tree(2 * n - 1), lazy(2 * n - 1) {}
template <typename Vec>
void build(int x, int l, int r, const Vec& v) {
if (l == r - 1) {
tree[x] = T::from_value(v[l]);
return;
}
int m = (l + r) / 2, y = x + 1, z = x + (m - l) * 2;
build(y, l, m, v);
build(z, m, r, v);
tree[x] = F()(tree[y], tree[z]);
}
template <typename Vec>
SegmentTree(const Vec& v) : SegmentTree(static_cast<int>(v.size())) {
build(0, 0, n, v);
}
inline void apply(int x, const L& t) {
tree[x].apply(t);
lazy[x].apply(t);
}
inline void push(int x, int y, int z) {
apply(y, lazy[x]);
apply(z, lazy[x]);
lazy[x] = L();
}
inline void pull(int x, int y, int z) {
tree[x] = F()(tree[y], tree[z]);
}
void modify(int x, int l, int r, int p, const T& v) {
if (l == r - 1) {
tree[x] = v;
return;
}
int m = (l + r) / 2, y = x + 1, z = x + (m - l) * 2;
push(x, y, z);
if (p < m)
modify(y, l, m, p, v);
else
modify(z, m, r, p, v);
pull(x, y, z);
}
void range_apply(int x, int l, int r, int ql, int qr, const L& t) {
if (ql <= l && r <= qr) {
apply(x, t);
return;
}
int m = (l + r) / 2, y = x + 1, z = x + (m - l) * 2;
push(x, y, z);
if (m > ql) range_apply(y, l, m, ql, qr, t);
if (m < qr) range_apply(z, m, r, ql, qr, t);
pull(x, y, z);
}
T range_query(int x, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return tree[x];
}
int m = (l + r) / 2, y = x + 1, z = x + (m - l) * 2;
push(x, y, z);
if (m <= ql) return range_query(z, m, r, ql, qr);
if (m >= qr) return range_query(y, l, m, ql, qr);
return F()(range_query(y, l, m, ql, qr), range_query(z, m, r, ql, qr));
}
inline void modify(int p, const T& v) {
assert(0 <= p && p < n);
modify(0, 0, n, p, v);
}
// NOTE: [l, r)
inline void range_apply(int l, int r, const L& t) {
assert(0 <= l && l < r && r <= n);
range_apply(0, 0, n, l, r, t);
}
// NOTE: [l, r)
inline T range_query(int l, int r) {
assert(0 <= l && l < r && r <= n);
return range_query(0, 0, n, l, r);
}
};
struct Tag {
int l = 0, r = 1e9; // make become this
inline void apply(const Tag& t) {
if (t.l >= r) {
l = t.l;
r = t.l;
return;
}
if (t.r <= l) {
l = t.r;
r = t.r;
return;
}
if (l < t.l) {
l = t.l;
}
if (r > t.r) {
r = t.r;
}
}
};
struct Info {
int max_val = 0;
inline void apply(const Tag& t) {
if (max_val < t.l) {
max_val = t.l;
}
if (max_val > t.r) {
max_val = t.r;
}
}
friend Info operator+(const Info& l, const Info& r) {
return {l.max_val < r.max_val ? r.max_val : l.max_val};
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
int finalHeight[]) {
SegmentTree<Info, Tag> tree(n);
for (int i = 0; i < k; i++) {
Tag val;
if (op[i] == 1) {
val.l = height[i];
} else {
val.r = height[i];
}
tree.range_apply(left[i], right[i] + 1, val);
}
for (int i = 0; i < n; i++) {
finalHeight[i] = tree.range_query(i, i + 1).max_val;
}
}
