#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> mx, mn, wl, wr;
int p, dp, r = 2147483647;
void ac(int i, int x, int n)
{
if (x > mn[i])
mx[i] = mn[i] = x;
else if (n < mx[i])
mx[i] = mn[i] = n;
else
{
mx[i] = max(mx[i], x);
mn[i] = min(mn[i], n);
}
}
void push(int i)
{
if (i >= p)
return;
ac(i << 1, mx[i], mn[i]);
ac((i << 1) ^ 1, mx[i], mn[i]);
mx[i] = 0;
mn[i] = r;
}
void upd(int l, int r, int i, int x, int n)
{
push(i);
if (wl[i] >= r || wr[i] <= l)
return;
if (wl[i] >= l && wr[i] <= r)
{
ac(i, x, n);
return;
}
upd(l, r, i << 1, x, n);
upd(l, r, (i << 1) ^ 1, x, n);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
p = n;
while (p != (p & -p))
p++;
dp = (p << 1);
int i;
pair<int, int> t;
mx.resize(dp);
mn.resize(dp);
wl.resize(dp);
wr.resize(dp);
for (i = p; i < dp; i++)
{
mx[i] = mn[i] = 0;
wl[i] = i;
wr[i] = i + 1;
}
for (i = p - 1; i > 0; i--)
{
mx[i] = mn[i] = 0;
wl[i] = wl[i << 1];
wr[i] = wr[(i << 1) ^ 1];
}
for (i = 0; i < k; i++)
{
if (op[i] == 1)
upd(left[i] + p, right[i] + p + 1, 1, height[i], r);
else
upd(left[i] + p, right[i] + p + 1, 1, 0, height[i]);
}
for (i = 1; i < p; i++)
push(i);
for (i = 0; i < n; i++)
finalHeight[i] = mx[i + p];
return;
}
