#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int OO = (int)1e18;
struct SegMonoid {
int lo = 0, hi = 0;
SegMonoid (int initLo, int initHi) {
lo = initLo, hi = initHi;
}
void combineNew (SegMonoid other) {
if (hi < other.lo) {
lo = other.lo, hi = other.lo;
}
else if (other.hi < lo) {
lo = other.hi, hi = other.hi;
}
else {
lo = max(lo, other.lo), hi = min(hi, other.hi);
}
}
void print () {
cerr << "[" << lo << ", " << hi << "]";
}
};
SegMonoid combineSegMonoid (SegMonoid a, SegMonoid b) {
return SegMonoid(min(a.lo, b.lo), max(a.hi, b.hi));
}
struct Segtree {
int numleaves;
vector<SegMonoid> tree;
Segtree (int n) {
numleaves = 1;
while (numleaves < n) numleaves *= 2;
tree.assign(2*numleaves, SegMonoid(0, 0));
}
void pushdown (int node) {
if (node < numleaves) {
tree[2*node].combineNew(tree[node]);
tree[2*node+1].combineNew(tree[node]);
}
}
void update (int node, int nL, int nR, int qL, int qR, SegMonoid newInter) {
pushdown(node);
if (qL <= nL && nR <= qR) {
tree[node].combineNew(newInter);
pushdown(node);
}
else if (nR < qL || qR < nL) {
return;
}
else {
int nMid = nL + (nR - nL) / 2;
update(2*node, nL, nMid, qL, qR, newInter);
update(2*node+1, nMid+1, nR, qL, qR, newInter);
tree[node] = combineSegMonoid(tree[2*node], tree[2*node+1]);
}
}
void update (int qL, int qR, SegMonoid newInter) {
update(1, 0, numleaves-1, qL, qR, newInter);
}
int get (int idx) {
int node = 1, nL = 0, nR = numleaves-1;
while (node < numleaves) {
pushdown(node);
int nMid = nL + (nR - nL) / 2;
if (nL <= idx && idx <= nMid) {
nR = nMid;
node = 2*node;
}
else {
nL = nMid+1;
node = 2*node+1;
}
}
return tree[node].lo;
}
void dbg () {
cerr << "Tree:\n";
for (int h = 0; h <= log2(numleaves); h++) {
for (int i = (1 << h); i < (1 << (h+1)); i++) {
tree[i].print();cerr << " ";
}
cerr << "\n";
}
cerr << "Wall:\n";
for (int i = 0; i < numleaves; i++) cerr << get(i) << " ";
cerr << "\n";
}
};
void buildWall(int N, int Q, int typeQ[], int leftQ[], int rightQ[], int heightQ[], int finalHeight[]){
Segtree wall(N);
for (int q = 0; q < Q; q++) {
if (typeQ[q] == 1) { // add
wall.update(leftQ[q], rightQ[q], SegMonoid(heightQ[q], OO));
}
else { // rem
wall.update(leftQ[q], rightQ[q], SegMonoid(0, heightQ[q]));
}
}
for (int i = 0; i < N; i++) {
finalHeight[i] = wall.get(i);
}
}
