#include "wall.h"
#include <algorithm>
using namespace std;
const int MAXN = 2000005;
struct SEG {
int max, min;
} seg[4 * MAXN];
int n;
void push(int x) {
int L = x * 2, R = x * 2 + 1;
seg[L].min = min(max(seg[L].min, seg[x].min), seg[x].max);
seg[R].min = min(max(seg[R].min, seg[x].min), seg[x].max);
seg[L].max = max(min(seg[L].max, seg[x].max), seg[x].min);
seg[R].max = max(min(seg[R].max, seg[x].max), seg[x].min);
}
void query(int x, int s, int e, int l, int r, int h, int op) {
if (s > e) return;
if (e < l || r < s) return;
if (l <= s && e <= r) {
if (op == 1) {
seg[x].min = max(seg[x].min, h);
seg[x].max = max(seg[x].max, h);
}
else {
seg[x].max = min(seg[x].max, h);
seg[x].min = min(seg[x].min, h);
}
return;
}
if (s < e) {
int m = (s + e) / 2;
push(x);
query(x * 2, s, m, l, r, h, op);
query(x * 2 + 1, m + 1, e, l, r, h, op);
seg[x].max = max(seg[x * 2].max, seg[x * 2 + 1].max);
seg[x].min = min(seg[x * 2].min, seg[x * 2 + 1].min);
}
}
int ans[MAXN];
void dfs(int x, int s, int e) {
if (s > e) return;
if (s == e) {
ans[s] = seg[x].max;
return;
}
push(x);
int m = (s + e) / 2;
dfs(x * 2, s, m);
dfs(x * 2 + 1, m + 1, e);
}
void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
n = _n;
for (int i = 0; i < k; i++) {
query(1, 0, n - 1, left[i], right[i], height[i], op[i]);
}
dfs(1, 0, n - 1);
for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
return;
}
