#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = int;
struct Query {
ll mn = 0;
ll mx = 1e9;
};
template <typename T> class LazySegtree {
private:
const int sz;
vector<Query> tree; // tree[i] = sum of this node's range
vector<Query> lazy; // lazy[i] = lazy update for the range
/** builds the segtree nodes */
void build(int v, int l, int r, const vector<T> &a) {
if (l == r) {
tree[v].mn = a[l];
tree[v].mx = a[l];
} else {
int m = (l + r) / 2;
build(2 * v, l, m, a);
build(2 * v + 1, m + 1, r, a);
tree[v].mn = min(tree[2*v].mn, tree[2*v+1].mn);
tree[v].mx = max(tree[2*v].mx, tree[2*v+1].mx);
}
}
/** applies lazy update to tree[v], places update at lazy[v] */
void apply(int v, int len, const Query &x) {
ll maxz = x.mx;
ll minz = x.mn;
ll maxv = lazy[v].mx;
ll minv = lazy[v].mn;
if (maxz < tree[v].mn) {
tree[v].mx = maxz;
tree[v].mn = maxz;
} else if (minz > tree[v].mx) {
tree[v].mx = minz;
tree[v].mn = minz;
} else {
tree[v].mx = min(maxz, tree[v].mx);
tree[v].mn = max(minz, tree[v].mn);
}
if (maxz < minv) {
lazy[v].mx = maxz;
lazy[v].mn = maxz;
} else if (minz > maxv) {
lazy[v].mx = minz;
lazy[v].mn = minz;
} else {
lazy[v].mx = min(maxz, maxv);
lazy[v].mn = max(minz, minv);
}
}
/** pushes down lazy update to children of v */
void push_down(int v, int l, int r) {
int m = (l + r) / 2;
apply(2 * v, m - l + 1, lazy[v]);
apply(2 * v + 1, r - m, lazy[v]);
lazy[v] = Query();
}
void range_update(int v, int l, int r, int ql, int qr, const Query &x) {
if (qr < l || ql > r) { return; }
if (ql <= l && r <= qr) {
apply(v, r - l + 1, x);
} else {
push_down(v, l, r);
int m = (l + r) / 2;
range_update(2 * v, l, m, ql, qr, x);
range_update(2 * v + 1, m + 1, r, ql, qr, x);
tree[v].mn = min(tree[2*v].mn, tree[2*v+1].mn);
tree[v].mx = max(tree[2*v].mx, tree[2*v+1].mx);
}
}
T query(int v, int l, int r, int ql) {
if (l == r) {
return tree[v].mn;
} else {
push_down(v, l, r);
int m = (l + r) / 2;
if (ql <= m) {
return query(2 * v, l, m, ql);
} else {
return query(2 * v + 1, m+1, r, ql);
}
}
}
public:
LazySegtree(const vector<T> &a) : sz(a.size()), tree(4 * sz), lazy(4 * sz) {
build(1, 0, sz - 1, a);
}
/** updates [ql, qr] with the update x */
void range_update(int ql, int qr, const Query &x) {
range_update(1, 0, sz - 1, ql, qr, x);
}
/** sum of array values on [ql, qr] */
T query(int ql) { return query(1, 0, sz - 1, ql); }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int final_height[]) {
vector<ll> a(n, 0);
LazySegtree<ll> st(a);
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
st.range_update(left[i], right[i], Query{height[i], (ll)1e9});
} else {
st.range_update(left[i], right[i], {0, height[i]});
}
}
for (int i = 0; i < n; i++) {
// cout << "st.query(i): " << st.query(i) << "\n";
final_height[i] = st.query(i);
}
}
