#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const pair<int, int> base = {INF, -INF};
void minimize(pair<int, int> &A, int t)
{
A.first = min(A.first, t);
A.second = min(A.first, A.second);
}
void maximize(pair<int, int> &A, int t)
{
A.second = max(A.second, t);
A.first = max(A.second, A.first);
}
const int maxn = 2e6 + 5;
int a[maxn];
struct Segtree
{
pair<int, int> st[4 * maxn], lz[4 * maxn];
void init(int id, int l, int r)
{
if (l == r)
return st[id] = lz[id] = base, void();
int mid = (l + r) >> 1;
init(id * 2, l, mid);
init(id * 2 + 1, mid + 1, r);
st[id] = st[id * 2];
minimize(st[id], st[id * 2 + 1].first);
maximize(st[id], st[id * 2 + 1].second);
}
void push(int id)
{
pair<int, int> &t = lz[id];
if (t == base)
return;
minimize(st[id * 2], t.first);
maximize(st[id * 2], t.second);
minimize(lz[id * 2], t.first);
maximize(lz[id * 2], t.second);
minimize(st[id * 2 + 1], t.first);
maximize(st[id * 2 + 1], t.second);
minimize(lz[id * 2 + 1], t.first);
maximize(lz[id * 2 + 1], t.second);
t = base;
}
void update(int id, int l, int r, int u, int v, int t, int type)
{
if (l == u && r == v)
{
if (type == 2)
minimize(st[id], t),
minimize(lz[id], t);
else
maximize(st[id], t),
maximize(lz[id], t);
return;
}
int mid = (l + r) >> 1;
push(id);
if (v <= mid)
update(id * 2, l, mid, u, v, t, type);
else if (u > mid)
update(id * 2 + 1, mid + 1, r, u, v, t, type);
else
{
update(id * 2, l, mid, u, mid, t, type);
update(id * 2 + 1, mid + 1, r, mid + 1, v, t, type);
}
st[id] = st[id * 2];
minimize(st[id], st[id * 2 + 1].first);
maximize(st[id], st[id * 2 + 1].second);
}
pair<int, int> get(int id, int l, int r, int u, int v)
{
if (l == u && r == v)
return st[id];
int mid = (l + r) >> 1;
push(id);
if (v <= mid)
return get(id * 2, l, mid, u, v);
else if (u > mid)
return get(id * 2 + 1, mid + 1, r, u, v);
else
{
pair<int, int> L = get(id * 2, l, mid, u, mid);
pair<int, int> R = get(id * 2 + 1, mid + 1, r, mid + 1, v);
minimize(L, R.first);
maximize(L, R.second);
return L;
}
}
} Segtree;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
Segtree.init(1, 1, n);
for (int i = 0; i < k; ++i)
Segtree.update(1, 1, n, left[i] + 1, right[i] + 1, height[i], op[i]);
for (int i = 0; i < n; ++i)
{
pair<int, int> get = Segtree.get(1, 1, n, i + 1, i + 1);
finalHeight[i] = get.second;
}
return;
}
