#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2000005;
const int INF = 1000000000;
int ST[4 * N], lazyMax[4 * N], lazyMin[4 * N];
void init(int n)
{
for (int i = 1; i < 4 * n; i++)
{
ST[i] = 0;
lazyMax[i] = -1;
lazyMin[i] = INF;
}
}
void propagate(int node, int l, int r)
{
if (lazyMax[node] != -1)
{
ST[node] = max(ST[node], lazyMax[node]);
if (l != r)
{
int left = 2 * node, right = 2 * node + 1;
lazyMax[left] = max(lazyMax[left], lazyMax[node]);
lazyMax[right] = max(lazyMax[right], lazyMax[node]);
}
lazyMax[node] = -1;
}
if (lazyMin[node] != INF)
{
ST[node] = min(ST[node], lazyMin[node]);
if (l != r)
{
int left = 2 * node, right = 2 * node + 1;
lazyMin[left] = min(lazyMin[left], lazyMin[node]);
lazyMin[right] = min(lazyMin[right], lazyMin[node]);
}
lazyMin[node] = INF;
}
}
void updateMax(int node, int l, int r, int a, int b, int h)
{
propagate(node, l, r);
if (l > b || r < a)
{
return;
}
if (a <= l && r <= b)
{
lazyMax[node] = h;
propagate(node, l, r);
return;
}
int mid = (l + r) / 2, left = 2 * node, right = 2 * node + 1;
updateMax(left, l, mid, a, b, h);
updateMax(right, mid + 1, r, a, b, h);
ST[node] = max(ST[left], ST[right]);
}
void updateMin(int node, int l, int r, int a, int b, int h)
{
propagate(node, l, r);
if (l > b || r < a)
{
return;
}
if (a <= l && r <= b)
{
lazyMin[node] = h;
propagate(node, l, r);
return;
}
int mid = (l + r) / 2, left = 2 * node, right = 2 * node + 1;
updateMin(left, l, mid, a, b, h);
updateMin(right, mid + 1, r, a, b, h);
ST[node] = min(ST[left], ST[right]);
}
void buildFinalHeights(int node, int l, int r, int finalHeight[])
{
propagate(node, l, r);
if (l == r)
{
finalHeight[l] = ST[node];
return;
}
int mid = (l + r) / 2, left = 2 * node, right = 2 * node + 1;
buildFinalHeights(left, l, mid, finalHeight);
buildFinalHeights(right, mid + 1, r, finalHeight);
}
void buildWall(int n, int k, int op[], int leftArr[], int rightArr[], int height[], int finalHeight[])
{
init(n);
for (int i = 0; i < k; i++)
{
int a = leftArr[i], b = rightArr[i], h = height[i];
if (op[i] == 1)
{
updateMax(1, 0, n - 1, a, b, h);
}
else
{
updateMin(1, 0, n - 1, a, b, h);
}
}
buildFinalHeights(1, 0, n - 1, finalHeight);
}
