#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct segtree
{
private:
int n;
vector<int> mntree, mxtree;
vector<bool> lazy;
void comb(int v)
{
mntree[v] = min(mntree[2 * v], mntree[2 * v + 1]);
mxtree[v] = max(mxtree[2 * v], mxtree[2 * v + 1]);
}
void do_lazy(int v, int tl, int tr)
{
if (!lazy[v])
return;
if (tl != tr)
{
mntree[2 * v] = max(mntree[2 * v], mntree[v]);
mxtree[2 * v] = max(mxtree[2 * v], mntree[2 * v]);
mxtree[2 * v] = min(mxtree[2 * v], mxtree[v]);
mntree[2 * v] = min(mntree[2 * v], mxtree[2 * v]);
lazy[2 * v] = true;
mntree[2 * v + 1] = max(mntree[2 * v + 1], mntree[v]);
mxtree[2 * v + 1] = max(mxtree[2 * v + 1], mntree[2 * v + 1]);
mxtree[2 * v + 1] = min(mxtree[2 * v + 1], mxtree[v]);
mntree[2 * v + 1] = min(mntree[2 * v + 1], mxtree[2 * v + 1]);
lazy[2 * v + 1] = true;
}
lazy[v] = false;
}
void update_min(int l, int r, int h, int v, int tl, int tr)
{
do_lazy(v, tl, tr);
if (tr < l || r < tl)
return;
if (l <= tl && tr <= r)
{
mxtree[v] = min(mxtree[v], h);
mntree[v] = min(mntree[v], mxtree[v]);
lazy[v] = true;
return;
}
int m = (tl + tr) / 2;
update_min(l, r, h, 2 * v, tl, m);
update_min(l, r, h, 2 * v + 1, m + 1, tr);
comb(v);
}
void update_max(int l, int r, int h, int v, int tl, int tr)
{
do_lazy(v, tl, tr);
if (tr < l || r < tl)
return;
if (l <= tl && tr <= r)
{
mntree[v] = max(mntree[v], h);
mxtree[v] = max(mxtree[v], mntree[v]);
lazy[v] = true;
return;
}
int m = (tl + tr) / 2;
update_max(l, r, h, 2 * v, tl, m);
update_max(l, r, h, 2 * v + 1, m + 1, tr);
comb(v);
}
int query(int idx, int v, int tl, int tr)
{
do_lazy(v, tl, tr);
if (tl == tr)
return mntree[v];
else
{
int m = (tl + tr) / 2;
if (idx <= m)
return query(idx, 2 * v, tl, m);
else
return query(idx, 2 * v + 1, m + 1, tr);
}
}
public:
segtree(int _n)
{
n = _n;
mntree.resize(4 * n, 0);
mxtree.resize(4 * n, 0);
lazy.resize(4 * n, false);
}
void update_max(int l, int r, int h)
{
if (l > r)
swap(l, r);
update_max(l, r, h, 1, 0, n - 1);
}
void update_min(int l, int r, int h)
{
if (l > r)
swap(l, r);
update_min(l, r, h, 1, 0, n - 1);
}
int query(int idx)
{
return query(idx, 1, 0, n - 1);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
segtree tree(n);
for (int i = 0; i < k; i++)
{
if (op[i] == 1)
tree.update_max(left[i], right[i], height[i]);
else
tree.update_min(left[i], right[i], height[i]);
// for (int i = 0; i < n; i++)
// cout << tree.query(i) << ' ';
// cout << endl;
}
for (int i = 0; i < n; i++)
finalHeight[i] = tree.query(i);
return;
}
