#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int INF = 1e9;
const int N = 2e6 + 10;
int ka[4 * N], ki[4 * N];
bool ish[4 * N];
int n;
void minim(int, int, int, int, int, int);
void maxim(int, int, int, int, int, int);
void init() {
for (int i = 0; i < N; i++) {
ka[i] = 0;
ki[i] = INF;
}
}
void minim(int v, int l, int r, int tl, int tr, int h) {
if (tr < l || r < tl) return;
if (tl <= l && r <= tr) {
ki[v] = min(ki[v], h);
ka[v] = min(ka[v], ki[v]);
ish[v] = 1;
return;
}
int m = (l + r) / 2;
if (ish[v]) {
ish[v] = 0;
ish[2 * v] = ish[2 * v + 1] = 1;
maxim(2 * v, l, m, l, m, ka[v]);
minim(2 * v, l, m, l, m, ki[v]);
maxim(2 * v + 1, m + 1, r, m + 1, r, ka[v]);
minim(2 * v + 1, m + 1, r, m + 1, r, ki[v]);
ka[v] = 0;
ki[v] = INF;
}
minim(2 * v, l, m, tl, tr, h);
minim(2 * v + 1, m + 1, r, tl, tr, h);
}
void maxim(int v, int l, int r, int tl, int tr, int h) {
if (tr < l || r < tl) return;
if (tl <= l && r <= tr) {
ka[v] = max(ka[v], h);
ki[v] = max(ki[v], ka[v]);
ish[v] = 1;
return;
}
int m = (l + r) / 2;
if (ish[v]) {
ish[v] = 0;
ish[2 * v] = ish[2 * v + 1] = 1;
minim(2 * v, l, m, l, m, ki[v]);
maxim(2 * v, l, m, l, m, ka[v]);
minim(2 * v + 1, m + 1, r, m + 1, r, ki[v]);
maxim(2 * v + 1, m + 1, r, m + 1, r, ka[v]);
ka[v] = 0;
ki[v] = INF;
}
maxim(2 * v, l, m, tl, tr, h);
maxim(2 * v + 1, m + 1, r, tl, tr, h);
}
int get(int v, int l, int r, int x) {
if (l == r) {
return ka[v];
}
int m = (l + r) / 2;
if (x <= m)
return get(2 * v, l, m, x);
else
return get(2 * v + 1, m + 1, r, x);
}
void buildWall(int nn, int k, int op[], int left[], int right[], int height[],
int finalHeight[]) {
n = nn;
init();
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
maxim(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
} else {
minim(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
}
}
for (int i = 1; i <= n; i++) {
minim(1, 1, n, i, i, INF);
// maxim(1, 1, n, i, i, 0);
finalHeight[i - 1] = get(1, 1, n, i);
}
return;
}
