#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N = 2e6 + 10;
int a[N], mn[N << 2], mx[N << 2];
void applymin(int node, int h) {
mn[node] = min(mn[node], h);
mx[node] = min(mx[node], mn[node]);
}
void applymax(int node, int h) {
mx[node] = max(mx[node], h);
mn[node] = max(mn[node], mx[node]);
}
void shift(int node) {
applymin(node << 1, mn[node]);
applymin(node << 1 | 1, mn[node]);
applymax(node << 1, mx[node]);
applymax(node << 1 | 1, mx[node]);
mx[node] = 0;
mn[node] = INT_MAX;
}
void update(int node, int l, int r, int op, int i, int j, int h) {
if(r < i || l > j) return;
if(i <= l && r <= j) {
if(op == 1) applymax(node, h);
else applymin(node, h);
return;
} shift(node);
int m = l + r >> 1;
update(node << 1, l, m, op, i, j, h);
update(node << 1 | 1, m + 1, r, op, i, j, h);
}
void get(int node, int l, int r) {
if(l == r) {
a[l] = min(a[l], mn[node]);
a[l] = max(a[l], mx[node]);
return;
} int m = l + r >> 1;
shift(node);
get(node << 1, l, m);
get(node << 1 | 1, m + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
fill(mn, mn + (n << 2), INT_MAX);
fill(mx, mx + (n << 2), 0);
for(int i = 0; i < k; i++) {
update(1, 0, n - 1, op[i], left[i], right[i], height[i]);
} get(1, 0, n - 1);
for(int i = 0; i < n; i++)
finalHeight[i] = a[i];
}
