#include <bits/stdc++.h>
using namespace std;
// Estructura para representar un intervalo [l, r] con un valor "val".
struct Interval {
int l, r, val;
Interval(int _l, int _r, int _val) : l(_l), r(_r), val(_val) {}
};
// Comparador para ordenar intervalos por su límite izquierdo.
struct IntervalCompare {
bool operator()(const Interval &a, const Interval &b) const {
return a.l < b.l;
}
};
/*
Función buildWall:
n : número de columnas (índices 0 .. n-1).
k : número de fases.
op[] : para cada fase, 1 indica fase de "adding" y 2 fase de "removing".
leftArr[] : columna inicial (inclusive) de la fase.
rightArr[]: columna final (inclusive) de la fase.
heightArr[]: el parámetro de altura de la fase.
finalHeight[]: salida; al terminar se debe tener finalHeight[i] = número final de ladrillos en la columna i.
*/
void buildWall(int n, int k, int op[], int leftArr[], int rightArr[],
int heightArr[], int finalHeight[]) {
// Mantenemos la pared como un conjunto de intervalos ordenados por su inicio.
set<Interval, IntervalCompare> intervals;
intervals.insert(Interval(0, n - 1, 0)); // inicialmente todas las columnas tienen 0 ladrillos.
// Función lambda "split": dado un índice pos (0 <= pos <= n),
// se asegura que exista un intervalo que comience exactamente en pos.
auto split = [&](int pos) -> set<Interval, IntervalCompare>::iterator {
if (pos > n - 1) return intervals.end();
// Busca el primer intervalo cuyo inicio sea >= pos.
auto it = intervals.lower_bound(Interval(pos, 0, 0));
if (it != intervals.end() && it->l == pos)
return it;
// Si el intervalo que contiene pos empieza antes, retrocedemos.
it--;
int L = it->l, R = it->r, v = it->val;
if (pos > R) return intervals.end(); // no debería ocurrir
intervals.erase(it);
// Dividimos el intervalo en [L, pos-1] y [pos, R].
intervals.insert(Interval(L, pos - 1, v));
return intervals.insert(Interval(pos, R, v)).first;
};
// Función lambda para fusionar (merge) intervalos adyacentes que tengan el mismo valor.
// Se “recorre” desde un índice dado hasta el final de la pared.
auto mergeFrom = [&]() {
if (intervals.empty()) return;
auto it = intervals.begin();
while (it != intervals.end()) {
auto next = it; next++;
if (next == intervals.end()) break;
// Si son adyacentes y tienen el mismo valor, se fusionan.
if (it->r + 1 == next->l && it->val == next->val) {
int L = it->l, R = next->r, v = it->val;
// Borramos ambos intervalos y reinsertamos el fusionado.
intervals.erase(it);
intervals.erase(next);
auto inserted = intervals.insert(Interval(L, R, v)).first;
// Retrocedemos, por si se puede fusionar con el intervalo anterior.
it = inserted;
if (it != intervals.begin()) {
auto prev = it; prev--;
if (prev->r + 1 == it->l && prev->val == it->val) {
// Se fusiona con el anterior.
L = prev->l; R = it->r; v = it->val;
intervals.erase(prev);
intervals.erase(it);
it = intervals.insert(Interval(L, R, v)).first;
}
}
continue; // volvemos a probar con "it" en su nueva forma.
} else {
it++;
}
}
};
// Procesamos cada fase.
for (int i = 0; i < k; i++) {
int phaseType = op[i]; // 1: add, 2: remove.
int L = leftArr[i];
int R = rightArr[i];
int h = heightArr[i];
// Dividimos en los puntos L y R+1 para aislar la región [L, R].
auto itR = split(R + 1);
auto itL = split(L);
// Recorremos todos los intervalos que caen en [L, R] y actualizamos su valor si corresponde.
vector<Interval> updated; // para almacenar (l, r, nuevo_valor)
auto it = itL;
while (it != itR) {
int curVal = it->val;
int newVal = curVal;
if (phaseType == 1) { // add: si curVal < h, se sube a h.
if (curVal < h)
newVal = h;
} else { // remove: si curVal > h, se baja a h.
if (curVal > h)
newVal = h;
}
updated.push_back(Interval(it->l, it->r, newVal));
it++;
}
// Borramos los intervalos que se van a actualizar.
it = itL;
while (it != itR) {
auto tmp = it;
it++;
intervals.erase(tmp);
}
// Insertamos los intervalos actualizados.
for (auto &in : updated)
intervals.insert(in);
// Luego, se puede haber generado “huecos” de intervalos adyacentes con el mismo valor.
// Realizamos una fusión global.
mergeFrom();
}
// Finalmente, rellenamos finalHeight[] usando los intervalos resultantes.
for (auto it = intervals.begin(); it != intervals.end(); it++) {
for (int j = it->l; j <= it->r; j++)
finalHeight[j] = it->val;
}
}
