#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
struct val
{
int minv = 0, maxv = 100'000;
val operator+(const val &b)
{
val a = *this, res;
res.minv = max(a.minv, b.minv);
res.maxv = min(a.maxv, b.maxv);
if (b.minv > maxv)
res.maxv = b.minv;
if (b.maxv < minv)
res.minv = b.maxv;
return res;
}
val &operator+=(const val &b)
{
minv = max(minv, b.minv);
maxv = min(maxv, b.maxv);
if (b.minv > maxv)
maxv = b.minv;
if (b.maxv < minv)
minv = b.maxv;
return *this;
}
};
vector<val> tree, lazy;
int treeN = 1;
void pull(int i)
{
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
void push(int i)
{
tree[i] += lazy[i];
if (i < treeN)
{
lazy[2 * i] += lazy[i];
lazy[2 * i + 1] += lazy[i];
}
lazy[i] = {};
}
val query(int i, int l, int r, int ql, int qr, int v, int op)
{
push(i);
if (qr < l || r < ql)
return {};
if (ql <= l && r <= qr)
{
if (op == 1)
{
val add = {v, 100'000};
lazy[i] += add;
push(i);
}
else if (op == 2)
{
val add = {0, v};
lazy[i] += add;
push(i);
}
return tree[i];
}
int m = (l + r) / 2;
val res = query(2 * i, l, m, ql, qr, v, op) +
query(2 * i + 1, m + 1, r, ql, qr, v, op);
pull(i);
return res;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
while (treeN < n)
treeN *= 2;
tree = lazy = vector<val>(treeN * 2);
for (int i = 0; i < k; i++)
{
int l = left[i], r = right[i], h = height[i];
query(1, 0, treeN - 1, l, r, h, op[i]);
}
for (int i = 0; i < n; i++)
{
finalHeight[i] = query(1, 0, treeN - 1, i, i, 0, 0).minv;
}
return;
}
