#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
template <class T> using v = vector<T>;
struct Node {
int dec, inc;
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
// order matters
template <class T> struct Seg {
// TODO: implement
const T ID = {0, 0}; // comb(ID,b) = b
T comb(T a, T b) {}
int n;
v<T> seg;
void init(int _n) {
n = _n;
seg.assign(2 * n, ID);
}
void push(int p) {}
// 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) {
for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
if (l & 1)
seg[l++].cinc(val);
if (r & 1)
seg[--r].cinc(val);
}
}
void dec(int l, int r, int val) {
for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
if (l & 1)
seg[l++].cdec(val);
if (r & 1)
seg[--r].cdec(val);
}
}
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(n);
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]);
}
}
for (int i = 0; i < n; i++) {
finalHeight[i] = w.get(i).inc;
}
}
