#include <vector>
#include <iostream>
using namespace std;
int infinito = 2e9;
struct arbolDeSegmentos {
vector<pair<int, int>> intervalos;
arbolDeSegmentos(int n) {
intervalos.assign(4 * n, make_pair(0, infinito));
}
void aplicarCambio(int x, int nuevoMinimo, int nuevoMaximo) {
// Actualizamos el minimo
intervalos[x].first = max(intervalos[x].first, nuevoMinimo);
intervalos[x].second = max(intervalos[x].second, intervalos[x].first);
// Actualizamos el maximo
intervalos[x].second = min(intervalos[x].second, nuevoMaximo);
intervalos[x].first = min(intervalos[x].first, intervalos[x].second);
}
void propagarCambio(int x, int l, int r) {
if (l == r) return;
aplicarCambio(2*x, intervalos[x].first, intervalos[x].second);
aplicarCambio(2*x+1, intervalos[x].first, intervalos[x].second);
intervalos[x] = make_pair(0, infinito);
}
void cambiarMinimo(
int x,
int l,
int r,
int inicioIntervalo,
int finalIntervalo,
int nuevoMinimo
) {
if (r < inicioIntervalo || l > finalIntervalo) return;
if (inicioIntervalo <= l && r <= finalIntervalo) {
aplicarCambio(x, nuevoMinimo, infinito);
} else {
propagarCambio(x, l, r);
int mid = l + (r - l) / 2;
cambiarMinimo(
2*x, l, mid, inicioIntervalo, finalIntervalo, nuevoMinimo
);
cambiarMinimo(
2*x+1, mid+1, r, inicioIntervalo, finalIntervalo, nuevoMinimo
);
}
}
void cambiarMaximo(
int x,
int l,
int r,
int inicioIntervalo,
int finalIntervalo,
int nuevoMaximo
) {
if (r < inicioIntervalo || l > finalIntervalo) return;
if (inicioIntervalo <= l && r <= finalIntervalo) {
aplicarCambio(x, 0, nuevoMaximo);
} else {
propagarCambio(x, l, r);
int mid = l + (r - l) / 2;
cambiarMaximo(
2*x, l, mid, inicioIntervalo, finalIntervalo, nuevoMaximo
);
cambiarMaximo(
2*x+1, mid+1, r, inicioIntervalo, finalIntervalo, nuevoMaximo
);
}
}
int encontrarAltura(int x, int l, int r, int indiceBuscado) {
if (l == r) {
return intervalos[x].first; // == intervalos[x].second
} else {
propagarCambio(x, l, r);
int mid = l + (r - l) / 2;
if (indiceBuscado <= mid) {
return encontrarAltura(2*x, l, mid, indiceBuscado);
} else {
return encontrarAltura(2*x+1, mid+1, r, indiceBuscado);
}
}
}
};
void buildWall(
int n,
int k,
int op[],
int left[],
int right[],
int height[],
int finalHeight[])
{
arbolDeSegmentos arbol = arbolDeSegmentos(n);
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
arbol.cambiarMinimo(1, 0, n-1, left[i], right[i], height[i]);
} else {
arbol.cambiarMaximo(1, 0, n-1, left[i], right[i], height[i]);
}
}
for (int i = 0; i < n; i++) {
finalHeight[i] = arbol.encontrarAltura(1, 0, n-1, i);
}
}
