#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define f1 first
#define s2 second
using ii = pair<int, int>;
const int MAX = 2e6 + 69;
const int inf = 1e9 + 69;
ii st[1 << 22]; // [up, down]
void add(int p, int q, int u, int d, int node, int l, int r)
{
if (l > q || r < p)
return;
if (p <= l && r <= q)
{
st[node].f1 = max(st[node].f1, u);
st[node].s2 = max(st[node].s2, u);
st[node].f1 = min(st[node].f1, d);
st[node].s2 = min(st[node].s2, d);
return;
}
int mid = (l + r) >> 1;
st[node << 1].f1 = max(st[node << 1].f1, st[node].f1);
st[node << 1].f1 = min(st[node << 1].f1, st[node].s2);
st[node << 1].s2 = max(st[node << 1].s2, st[node].f1);
st[node << 1].s2 = min(st[node << 1].s2, st[node].s2);
st[node << 1 | 1].f1 = max(st[node << 1 | 1].f1, st[node].f1);
st[node << 1 | 1].f1 = min(st[node << 1 | 1].f1, st[node].s2);
st[node << 1 | 1].s2 = max(st[node << 1 | 1].s2, st[node].f1);
st[node << 1 | 1].s2 = min(st[node << 1 | 1].s2, st[node].s2);
st[node] = { 0, inf };
add(p, q, u, d, node << 1, l, mid);
add(p, q, u, d, node << 1 | 1, mid+1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
fill(st, st + (1 << 22), mp(0, inf));
for (int i = 0; i < k; ++i)
{
if (op[i] == 1)
add(left[i], right[i], height[i], inf, 1, 0, n-1);
else add(left[i], right[i], 0, height[i], 1, 0, n-1);
}
const auto getAns = [&](const auto &self, int node, int l, int r) -> void
{
if (l == r)
{
finalHeight[l] = min(st[node].f1, st[node].s2);
return;
}
int mid = (l + r) >> 1;
st[node << 1].f1 = max(st[node << 1].f1, st[node].f1);
st[node << 1].f1 = min(st[node << 1].f1, st[node].s2);
st[node << 1].s2 = max(st[node << 1].s2, st[node].f1);
st[node << 1].s2 = min(st[node << 1].s2, st[node].s2);
st[node << 1 | 1].f1 = max(st[node << 1 | 1].f1, st[node].f1);
st[node << 1 | 1].f1 = min(st[node << 1 | 1].f1, st[node].s2);
st[node << 1 | 1].s2 = max(st[node << 1 | 1].s2, st[node].f1);
st[node << 1 | 1].s2 = min(st[node << 1 | 1].s2, st[node].s2);
st[node] = { 0, inf };
self(self, node << 1, l, mid);
self(self, node << 1 | 1, mid+1, r);
};
getAns(getAns, 1, 0, n-1);
return;
}
