#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define fi first
#define se second
const int ADD = 1;
const int DEL = 2;
const int N = 2e6 + 5;
const int INF = 1e9+10;
int mn[N * 4], mx[N * 4];
int* H;
// i <= j
int clamp(int x, int i, int j) {
return min(max(x, i), j);
}
void pull(int u) {
int p = u >> 1;
mx[u] = clamp(mx[u], mn[p], mx[p]);
mn[u] = clamp(mn[u], mn[p], mx[p]);
}
void update(int u, int L, int R, int i, int j, int op, int x) {
if(j < L || R < i) {
return;
}
if(i <= L && R <= j) {
if(op == ADD) {
mn[u] = max(mn[u], x);
mx[u] = max(mx[u], mn[u]);
} else {
mx[u] = min(mx[u], x);
mn[u] = min(mn[u], mx[u]);
}
if(L == R) {
H[L] = clamp(0, mn[u], mx[u]);
}
} else {
int mid = (L + R) >> 1;
pull(u * 2);
pull(u * 2 + 1);
mn[u] = 0, mx[u] = INF;
update(u * 2, L, mid, i, j, op, x);
update(u * 2 + 1, mid + 1, R, i, j, op, x);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
fill(mx, mx + N * 4, 1e9 + 10);
H = finalHeight;
for(int i = 0; i < k; ++i) {
update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
}
for(int i = 0; i < n; ++i) {
update(1, 0, n - 1, i, i, ADD, 0);
}
}
