#include <iostream>
#include<algorithm>
#define M 0xfffff
#include "wall.h"
using namespace std;
struct seg {
int v, l, r, lzmn, lzmx;
} t[8000100];
void build(int i, int l, int r) {
t[i] = { 0, l, r, M, 0 };
if (l ^ r)
build(i * 2, l, l + r >> 1), build(i * 2 + 1, l + r + 2 >> 1, r);
}
void cmn(int i, int v) {
t[i].lzmn = min(t[i].lzmn, v);
t[i].lzmx = min(t[i].lzmx, v);
}
void cmx(int i, int v) {
t[i].lzmn = max(t[i].lzmn, v);
t[i].lzmx = max(t[i].lzmx, v);
}
void pd(int i) {
if (t[i].lzmn != M) {
if (t[i].l != t[i].r)
cmn(i * 2, t[i].lzmn), cmn(i * 2 + 1, t[i].lzmn);
else
t[i].v = min(t[i].v, t[i].lzmn);
t[i].lzmn = M;
}
if (t[i].lzmx) {
if (t[i].l != t[i].r)
cmx(i * 2, t[i].lzmx), cmx(i * 2 + 1, t[i].lzmx);
else
t[i].v = max(t[i].v, t[i].lzmx);
t[i].lzmx = 0;
}
}
void umn(int i, int l, int r, int v) {
if (l <= t[i].l && t[i].r <= r) {
cmn(i, v);
return;
}
pd(i);
if (t[i * 2].r < r)
umn(i * 2 + 1, l, r, v);
if (l <= t[i * 2].r)
umn(i * 2, l, r, v);
}
void umx(int i, int l, int r, int v) {
if (l <= t[i].l && t[i].r <= r) {
cmx(i, v);
return;
}
pd(i);
if (t[i * 2].r < r)
umx(i * 2 + 1, l, r, v);
if (l <= t[i * 2].r)
umx(i * 2, l, r, v);
}
int query(int i, int x) {
pd(i);
if (t[i].l == t[i].r)
return t[i].v;
if (t[i * 2].r < x)
return query(i * 2 + 1, x);
return query(i * 2, x);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
build(1, 0, n-1);
for (int i = 0; i < k; i++) {
(op[i]==1?umx:umn)(1, left[i], right[i], height[i]);
}
for (int i = 0; i < n; i++)
finalHeight[i] = query(1, i);
}
