#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << "[" << __LINE__ << "] " << #x << " = " << (x) << '\n';
template <class T> using v = vector<T>;
struct Node {
int dec, inc;
// dec = 0
// inc = 9
// -> dec=9, inc=9
//
void cinc(int val) {
if (dec < val) {
dec = val;
}
inc = max(inc, val);
}
void cdec(int val) {
if (inc > val) {
inc = val;
}
dec = min(dec, val);
}
};
// h=0, increase to 2, decrease to 1 -> 1
// h=0, decrease to 1, increase to 2 -> 2
// dec>=inc holds
// order matters
template <class T> struct Seg {
// TODO: implement
const T ID = {INT_MAX, -1}; // comb(ID,b) = b
T comb(T a, T b) { return {INT_MAX, -1}; }
int n;
v<T> seg;
void init(int _n) {
n = _n;
seg.assign(2 * n, ID);
}
void push(int p) {
if (seg[p].dec != INT_MAX) {
seg[2 * p].cdec(seg[p].dec);
seg[2 * p + 1].cdec(seg[p].dec);
seg[p].dec = INT_MAX;
}
if (seg[p].inc != -1) {
seg[2 * p].cinc(seg[p].inc);
seg[2 * p + 1].cinc(seg[p].inc);
seg[p].inc = -1;
}
}
// void pull(int p) { seg[p] = comb(seg[2 * p], seg[2 * p + 1]); }
void upd(int p, T val) { // set val at position p
seg[p += n] = val;
// for (p /= 2; p; p /= 2)
// pull(p);
}
void inc(int l, int r, int val) { inc(1, 0, n - 1, l, r, val); }
void inc(int p, int l, int r, int a, int b, int v) {
if (a > r || b < l)
return;
if (a <= l && r <= b) {
seg[p].cinc(v);
return;
}
int mid = (l + r) / 2;
push(p);
inc(2 * p, l, mid, a, b, v);
inc(2 * p + 1, mid + 1, r, a, b, v);
// pull(p);
}
void dec(int l, int r, int val) { dec(1, 0, n - 1, l, r, val); }
void dec(int p, int l, int r, int a, int b, int v) {
if (a > r || b < l)
return;
if (a <= l && r <= b) {
seg[p].cdec(v);
return;
}
int mid = (l + r) / 2;
push(p);
dec(2 * p, l, mid, a, b, v);
dec(2 * p + 1, mid + 1, r, a, b, v);
// pull(p);
}
T get(int p) { return seg[p + n]; }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
int finalHeight[]) {
Seg<Node> w;
w.init(1 << (int)ceil(log2(n)));
for (int i = 0; i < n; i++) {
w.upd(i, {0, 0});
}
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
w.inc(left[i], right[i], height[i]);
} else {
w.dec(left[i], right[i], height[i]);
}
// cerr << w.get(3).inc << '\n';
}
for (int i = 1; i < w.n; i++) {
w.push(i);
// cerr << w.seg[0].inc << ';';
}
for (int i = 0; i < n; i++) {
finalHeight[i] = w.get(i).inc;
}
}
