//
// Created by Rico on 8/20/2021.
//
#include <iostream>
#include "wall.h"
const int MAX_LBEG2 = 4194304;
using namespace std;
int lbeg;
int sizes[MAX_LBEG2];
int mns[MAX_LBEG2], mxs[MAX_LBEG2];
void addto(int cmn, int cmx, int nmn, int nmx, int& fmn, int& fmx) {
if (nmn > cmx) {
fmn = fmx = nmn;
} else if (cmn > nmx) {
fmn = fmx = nmx;
} else {
fmn = max(cmn, nmn);
fmx = min(cmx, nmx);
}
}
void pushdown(int i) {
addto(mns[i << 1], mxs[i << 1], mns[i], mxs[i], mns[i << 1], mxs[i << 1]);
addto(mns[i << 1 ^ 1], mxs[i << 1 ^ 1], mns[i], mxs[i], mns[i << 1 ^ 1], mxs[i << 1 ^ 1]);
mns[i] = INT32_MIN;
mxs[i] = INT32_MAX;
}
void qadd(int i, int l, int r, const int& h) {
if (l >= sizes[i] || r <= 0) return;
if (l <= 0 && r >= sizes[i]) {
if (h > mxs[i]) {
mns[i] = mxs[i] = h;
} else {
mns[i] = max(mns[i], h);
}
return;
}
pushdown(i);
qadd(i << 1, l, r, h);
qadd(i << 1 ^ 1, l - sizes[i << 1], r - sizes[i << 1], h);
}
void qremove(int i, int l, int r, const int& h) {
if (l >= sizes[i] || r <= 0) return;
if (l <= 0 && r >= sizes[i]) {
if (h < mns[i]) {
mns[i] = mxs[i] = h;
} else {
mxs[i] = min(mxs[i], h);
}
return;
}
pushdown(i);
qremove(i << 1, l, r, h);
qremove(i << 1 ^ 1, l - sizes[i << 1], r - sizes[i << 1], h);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
for (lbeg = 1; lbeg < n; lbeg <<= 1);
fill(sizes + lbeg, sizes + (lbeg + n), 1);
fill(sizes + (lbeg + n), sizes + (lbeg << 1), 0);
for (int i = lbeg - 1; i > 0; --i) sizes[i] = sizes[i << 1] + sizes[i << 1 ^ 1];
fill(mns, mns + lbeg, INT32_MIN);
fill(mns + lbeg, mns + (lbeg << 1), 0);
fill(mxs, mxs + lbeg, INT32_MAX);
fill(mxs + lbeg, mxs + (lbeg << 1), 0);
for (int it = 0, type; it < k; ++it) {
type = op[it];
if (type == 1) {
qadd(1, left[it], right[it] + 1, height[it]);
} else if (type == 2) {
qremove(1, left[it], right[it] + 1, height[it]);
}
}
for (int i = 1; i < lbeg; ++i) {
pushdown(i);
}
for (int i = lbeg; i < lbeg + n; ++i) {
finalHeight[i - lbeg] = mns[i];
}
}
