#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct upd {
int l, r;
};
const int MAX_N = 2e6;
const int INF = 1e9;
vector<int> updatesByL[MAX_N], updatesByR[MAX_N];
upd segTree[4 * MAX_N];
void update(int v, int l, int r, int p, upd x) {
if (p > r || p < l)
return;
if (l == r) {
segTree[v] = x;
return;
}
int mid = (l + r) / 2;
update(v * 2 + 1, l, mid, p, x);
update(v * 2 + 2, mid + 1, r, p, x);
upd a = segTree[v * 2 + 1];
upd b = segTree[v * 2 + 2];
upd ans;
ans.l = min(max(a.l, b.l), b.r);
ans.r = min(max(a.r, b.l), b.r);
// printf("aint %d %d -> %d %d %d\n", l, r, a.l, a.r, a.k);
segTree[v] = ans;
}
upd queryAll() {
return segTree[0];
}
void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int v = 0; v < 4 * n; v++)
segTree[v] = {0, INF};
for (int i = 0; i < q; i++) {
updatesByL[left[i]].push_back(i);
updatesByR[right[i]].push_back(i);
}
for (int i = 0; i < n; i++) {
for (int j: updatesByL[i]) {
upd u;
if (op[j] == 1)
u = {height[j], INF};
else
u = {0, height[j]};
// printf("apare %d %d\n", op[j], height[j]);
update(0, 0, q - 1, j, u);
}
finalHeight[i] = queryAll().l;
// printf("query %d\n", i);
for (int j: updatesByR[i]) {
update(0, 0, q - 1, j, {0, INF});
// printf("dispare %d %d\n", op[j], height[j]);
}
}
}
