#include "wall.h"
#include <algorithm>
#include <utility>
#include <iostream>
#define pii pair<int, int>
#define fst first
#define snd second
using namespace std;
const int SZ = (1 << 22) + 5;
pii lz[SZ];
pii seg[SZ];
inline void prop(int idx, int L, int R)
{
if (L <= R)
{
if (seg[idx] != lz[idx])
{
seg[idx] = lz[idx];
if (L < R)
{
lz[2 * idx].fst = max(lz[2 * idx].fst, lz[idx].fst);
lz[2 * idx].snd = max(lz[2 * idx].snd, lz[idx].fst);
lz[2 * idx].fst = min(lz[2 * idx].fst, lz[idx].snd);
lz[2 * idx].snd = min(lz[2 * idx].snd, lz[idx].snd);
lz[2 * idx + 1].fst = max(lz[2 * idx + 1].fst, lz[idx].fst);
lz[2 * idx + 1].snd = max(lz[2 * idx + 1].snd, lz[idx].fst);
lz[2 * idx + 1].fst = min(lz[2 * idx + 1].fst, lz[idx].snd);
lz[2 * idx + 1].snd = min(lz[2 * idx + 1].snd, lz[idx].snd);
}
}
}
}
inline void merge(pii& p, const pii &l, const pii &r)
{
p = make_pair(min(l.fst, r.fst), max(l.snd, r.snd));
}
void upd(int idx, int L, int R, int l, int r, int t, int v)
{
prop(idx, L, R);
if (l <= r)
{
if (L == l && R == r)
{
if (t == 1)
{
lz[idx].fst = max(v, lz[idx].fst);
lz[idx].snd = max(v, lz[idx].snd);
}
else
{
lz[idx].fst = min(v, lz[idx].fst);
lz[idx].snd = min(v, lz[idx].snd);
}
prop(idx, L, R);
}
else
{
int M = L + R >> 1;
upd(2 * idx, L, M, l, min(M, r), t, v);
upd(2 * idx + 1, M + 1, R, max(M + 1, l), r, t, v);
merge(seg[idx], seg[2 * idx], seg[2 * idx + 1]);
lz[idx] = seg[idx];
}
}
//cout << "UPD [" << L << ", " << R << "] " << seg[idx].fst << ", " << seg[idx].snd << ", T = " << t << ", V = " << v << "\n";
}
inline int qry(int idx, int L, int R, int x)
{
prop(idx, L, R);
if (L == x && R == x) {return seg[idx].fst;}
else
{
int M = L + R >> 1;
if (x <= M) {return qry(2 * idx, L, M, x);}
else {return qry(2 * idx + 1, M + 1, R, x);}
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < k; i++)
{
upd(1, 0, n - 1, left[i], right[i], op[i], height[i]);
}
for (int i = 0; i < n; i++)
{
finalHeight[i] = qry(1, 0, n - 1, i);
}
return;
}
