#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 20;
const int maxn = 2e6 + 20;
pair<int, int> tree[maxn * 4];
void build(int id, int lt, int rt) {
if (lt == rt) {
tree[id] = make_pair(0, 0);
return;
}
tree[id] = make_pair(-inf, inf);
int mt = (lt + rt) / 2;
build(id * 2, lt, mt);
build(id * 2 + 1, mt + 1, rt);
}
void update(int id, int lt, int rt) {
if (tree[id].second < lt) {
tree[id] = make_pair(lt, lt);
}
else if (tree[id].first > rt) {
tree[id] = make_pair(rt, rt);
}
else {
tree[id] = make_pair(max(lt, tree[id].first), min(rt, tree[id].second));
}
}
void push(int id) {
update(id * 2, tree[id].first, tree[id].second);
update(id * 2 + 1, tree[id].first, tree[id].second);
tree[id] = make_pair(-inf, inf);
}
void update(int id, int lt, int rt, int ql, int qr, int op, int h) {
if (lt == ql && rt == qr) {
if (op == 1) {
update(id, h, inf);
}
else {
update(id, -inf, h);
}
return;
}
push(id);
int mt = (lt + rt) / 2;
if (qr <= mt) {
update(id * 2, lt, mt, ql, qr, op, h);
}
else if (ql >= mt + 1) {
update(id * 2 + 1, mt + 1, rt, ql, qr, op, h);
}
else {
update(id * 2, lt, mt, ql, mt, op, h);
update(id * 2 + 1, mt + 1, rt, mt + 1, qr, op, h);
}
}
int *finalHeight;
void push_all(int id, int lt, int rt) {
if (lt == rt) {
finalHeight[lt - 1] = tree[id].first;
return;
}
push(id);
int mt = (lt + rt) / 2;
push_all(id * 2, lt, mt);
push_all(id * 2 + 1, mt + 1, rt);
}
void buildWall(int n, int q, int op[], int left[], int right[], int height[], int _finalHeight[]) {
finalHeight = _finalHeight;
build(1, 1, n);
for (int i = 0; i < q; i++) {
update(1, 1, n, left[i] + 1, right[i] + 1, op[i], height[i]);
}
push_all(1, 1, n);
}
