#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int N;
int ans[2000000];
struct SegTree
{
int sz;
vector<pair<int, int>> st;
void init(int n)
{
sz = 1;
while (sz < n) sz <<= 1;
st.assign(sz << 1, {-1, 0});
}
void build(int l, int r, int x)
{
if (l + 1 == r)
{
st[x] = {0, 0};
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2*x + 1);
build(mid, r, 2*x + 2);
return;
}
void relax(int l, int r, int x)
{
if (l + 1 == r) return;
int l1 = st[x].first;
int r1 = st[x].second;
int l2 = st[2*x + 1].first;
int r2 = st[2*x + 1].second;
if (l1 >= r2) st[2*x + 1] = {l1, l1};
else if (r1 <= l2) st[2*x + 1] = {r1, r1};
else st[2*x + 1] = {max(l1, l2), min(r1, r2)};
l2 = st[2*x + 2].first, r2 = st[2*x + 2].second;
if (l1 >= r2) st[2*x + 2] = {l1, l1};
else if (r1 <= l2) st[2*x + 2] = {r1, r1};
else st[2*x + 2] = {max(l1, l2), min(r1, r2)};
st[x] = {0, 1e5};
}
void make(int l, int r, int x, int lx, int rx, int t, int val)
{
relax(l, r, x);
if (l >= rx || r <= lx) return;
if (l >= lx && r <= rx)
{
if (l + 1 == r)
{
if (t == 1) st[x] = {max(val, st[x].first), max(val, st[x].first)};
else st[x] = {min(val, st[x].first), min(val, st[x].first)};
return;
}
if (t == 1) st[x] = {val, 1e5};
else st[x] = {0, val};
relax(l, r, x);
return;
}
int mid = (l + r) >> 1;
make(l, mid, 2*x + 1, lx, rx, t, val);
make(mid, r, 2*x + 2, lx, rx, t, val);
return;
}
void final(int l, int r, int x)
{
if (l + 1 == r)
{
if (l < N) ans[l] = st[x].first;
return;
}
relax(l, r, x);
int mid = (l + r) >> 1;
final(l, mid, 2*x + 1);
final(mid, r, 2*x + 2);
return;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
SegTree st;
N = n;
st.init(n);
for (int q = 0; q < k; q++)
{
int t = op[q];
int lx = left[q];
int rx = right[q];
int val = height[q];
st.make(0, st.sz, 0, lx, rx + 1, t, val);
}
st.final(0, st.sz, 0);
for (int i = 0; i < n; i++)
{
finalHeight[i] = max(0, ans[i]);
}
}
