#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct state {
int min = -1, max = -1;
void merge(state &l, state &r) {
// min = std::max(l.min, r.min);
// max = std::min(r.min, l.min);
}
void push(state &l, state &r) {
// assert(min == -1 || max == -1);
if (min != -1) {
l.changeLower(min);
r.changeLower(min);
} else if (max != -1) {
l.changeUpper(max);
r.changeUpper(max);
}
min = max = -1;
}
void apply(pair<bool, int> &x) {
if (x.first) {
changeUpper(x.second);
} else {
changeLower(x.second);
}
}
void changeUpper(int x) {
if (max == -1) max = x;
else max = std::min(max, x);
if (min != -1) min = std::min(min, max);
}
void changeLower(int x) {
if (min == -1) min = x;
else min = std::max(min, x);
if (max != -1) max = std::max(max, min);
}
};
class lazyseg {
public:
vector<state> a;
int n;
lazyseg(int n) : n(n), a(4 * n) {}
void upd(int ll, int rr, int l, int r, int v, pair<bool, int> &x) {
if (r < ll || rr < l) return;
else if (ll <= l && r <= rr) a[v].apply(x);
else {
a[v].push(a[2 * v], a[2 * v + 1]);
int m = (l + r) / 2;
upd(ll, rr, l, m, 2 * v, x);
upd(ll, rr, m + 1, r, 2 * v + 1, x);
a[v].merge(a[2 * v], a[2 * v + 1]);
}
}
void finalize(int l, int r, int v, int *x) {
if (l == r) {
assert(a[v].max == -1 || (a[v].min <= a[v].max));
x[l] = max(0, max(a[v].min, min(a[v].max, x[l])));
} else {
a[v].push(a[2 * v], a[2 * v + 1]);
int m = (l + r) / 2;
finalize(l, m, 2 * v, x);
finalize(m + 1, r, 2 * v + 1, x);
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
lazyseg tree(n);
for (int i = 0; i < k; i++) {
pair<bool, int> update = {op[i] == 2, height[i]};
tree.upd(left[i], right[i], 0, n - 1, 1, update);
}
tree.finalize(0, n - 1, 1, finalHeight);
}
