#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int UPDATE_ID = 0;
const int INF = 1e9;
struct segtree
{
private:
int n;
vector<int> mntree, mxtree, mnlazy, mxlazy, mnid, mxid;
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 (mnid[v] > mxid[v])
{
if (mxid[v] != -1)
{
mxtree[v] = min(mxtree[v], mxlazy[v]);
mntree[v] = min(mntree[v], mxtree[v]);
}
if (mnid[v] != -1)
{
mntree[v] = max(mntree[v], mnlazy[v]);
mxtree[v] = max(mxtree[v], mntree[v]);
}
}
else
{
if (mnid[v] != -1)
{
mntree[v] = max(mntree[v], mnlazy[v]);
mxtree[v] = max(mxtree[v], mntree[v]);
}
if (mxid[v] != -1)
{
mxtree[v] = min(mxtree[v], mxlazy[v]);
mntree[v] = min(mntree[v], mxtree[v]);
}
}
if (tl != tr)
{
if (mxid[v] != -1)
{
mxid[2 * v] = mxid[v];
mxid[2 * v + 1] = mxid[v];
mxlazy[2 * v] = min(mxlazy[2 * v], mxlazy[v]);
mxlazy[2 * v + 1] = min(mxlazy[2 * v + 1], mxlazy[v]);
lazy[2 * v] = true;
lazy[2 * v + 1] = true;
}
if (mnid[v] != -1)
{
mnid[2 * v] = mnid[v];
mnid[2 * v + 1] = mnid[v];
mnlazy[2 * v] = max(mnlazy[2 * v], mnlazy[v]);
mnlazy[2 * v + 1] = max(mnlazy[2 * v + 1], mnlazy[v]);
lazy[2 * v] = true;
lazy[2 * v + 1] = true;
}
}
mxid[v] = mnid[v] = -1;
mnlazy[v] = -INF;
mxlazy[v] = INF;
lazy[v] = false;
}
void update_min(int l, int r, int h, int id, int v, int tl, int tr)
{
do_lazy(v, tl, tr);
if (tr < l || r < tl)
return;
if (l <= tl && tr <= r)
{
mxid[v] = id;
mxlazy[v] = h;
lazy[v] = true;
do_lazy(v, tl, tr);
return;
}
int m = (tl + tr) / 2;
update_min(l, r, h, id, 2 * v, tl, m);
update_min(l, r, h, id, 2 * v + 1, m + 1, tr);
comb(v);
}
void update_max(int l, int r, int h, int id, int v, int tl, int tr)
{
do_lazy(v, tl, tr);
if (tr < l || r < tl)
return;
if (l <= tl && tr <= r)
{
mnid[v] = id;
mnlazy[v] = h;
lazy[v] = true;
do_lazy(v, tl, tr);
return;
}
int m = (tl + tr) / 2;
update_max(l, r, h, id, 2 * v, tl, m);
update_max(l, r, h, id, 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);
mnlazy.resize(4 * n, -INF);
mxlazy.resize(4 * n, INF);
mnid.resize(4 * n, -1);
mxid.resize(4 * n, -1);
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, UPDATE_ID++, 1, 0, n - 1);
}
void update_min(int l, int r, int h)
{
if (l > r)
swap(l, r);
update_min(l, r, h, UPDATE_ID++, 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;
}
