#include "wall.h"
#include <vector>
using namespace std;
struct SegTree
{
int n;
vector<pair<int, int>> tree;
vector<pair<int, int>> mod;
SegTree(int _n) : n(_n)
{
tree.resize(4 * n + 5, {0, 1e5});
mod.resize(4 * n + 5, {0, 1e5});
}
void push(int v)
{
tree[v << 1].first = max(tree[v << 1].first, mod[v].first);
tree[v << 1].second = max(tree[v << 1].second, mod[v].first);
tree[v << 1 | 1].first = max(tree[v << 1 | 1].first, mod[v].first);
tree[v << 1 | 1].second = max(tree[v << 1 | 1].second, mod[v].first);
tree[v << 1].first = min(tree[v << 1].first, mod[v].second);
tree[v << 1].second = min(tree[v << 1].second, mod[v].second);
tree[v << 1 | 1].first = min(tree[v << 1 | 1].first, mod[v].second);
tree[v << 1 | 1].second = min(tree[v << 1 | 1].second, mod[v].second);
mod[v << 1].first = max(mod[v << 1].first, mod[v].first);
mod[v << 1].second = max(mod[v << 1].second, mod[v].first);
mod[v << 1 | 1].first = max(mod[v << 1 | 1].first, mod[v].first);
mod[v << 1 | 1].second = max(mod[v << 1 | 1].second, mod[v].first);
mod[v << 1].first = min(mod[v << 1].first, mod[v].second);
mod[v << 1].second = min(mod[v << 1].second, mod[v].second);
mod[v << 1 | 1].first = min(mod[v << 1 | 1].first, mod[v].second);
mod[v << 1 | 1].second = min(mod[v << 1 | 1].second, mod[v].second);
mod[v] = {0, 1e5};
}
void updateMax(int a, int b, int val, int v, int l, int r)
{
if (a > r || b < l) return;
if (a == l && b == r)
{
//make >= val
tree[v].first = max(tree[v].first, val);
tree[v].second = max(tree[v].second, val);
mod[v].first = max(mod[v].first, val);
mod[v].second = max(mod[v].second, val);
return;
}
push(v);
int m = (l + r) >> 1;
updateMax(a, min(b, m), val, v << 1, l, m);
updateMax(max(a, m + 1), b, val, v << 1 | 1, m + 1, r);
}
void updateMax(int a, int b, int val)
{
updateMax(a, b, val, 1, 0, n - 1);
}
void updateMin(int a, int b, int val, int v, int l, int r)
{
if (a > r || b < l) return;
if (a == l && b == r)
{
//make <= val
tree[v].first = min(tree[v].first, val);
tree[v].second = min(tree[v].second, val);
mod[v].first = min(mod[v].first, val);
mod[v].second = min(mod[v].second, val);
return;
}
push(v);
int m = (l + r) >> 1;
updateMin(a, min(b, m), val, v << 1, l, m);
updateMin(max(a, m + 1), b, val, v << 1 | 1, m + 1, r);
}
void updateMin(int a, int b, int val)
{
updateMin(a, b, val, 1, 0, n - 1);
}
pair<int, int> get(int p, int v, int l, int r)
{
if (l == r) return tree[v];
push(v);
int m = (l + r) >> 1;
if (p <= m) return get(p, v << 1, l, m);
return get(p, v << 1 | 1, m + 1, r);
}
int get(int p)
{
auto [l, r] = get(p, 1, 0, n - 1);
return l;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
SegTree st(n);
for (int i = 0; i < k; ++i)
{
if (op[i] == 1) st.updateMax(left[i], right[i], height[i]);
else st.updateMin(left[i], right[i], height[i]);
}
for (int i = 0; i < n; ++i) finalHeight[i] = st.get(i);
}
