Skip to Content
CTRL K

2014 - Wall

Análisis oficial 

Pista

Consideremos tratar cada actualización como una restricción sobre los valores que pueden tomar los elementos del rango. Por ejemplo, una actualización de rango add(x)\texttt{add(x)} restringe los valores del rango a ser ≥x\geq x, y una actualización de rango remove(x)\texttt{remove(x)} restringe los valores del rango a ser ≤x\leq x.

Explicación

Como se mencionó en la pista, podemos tratar cada actualización de rango como una restricción de qué valores pueden ocurrir en el rango. Por ejemplo, consideremos la siguiente secuencia de actualizaciones:

add(5)\texttt{add(5)}, remove(7)\texttt{remove(7)}

Entonces, cualquier valor del rango quedaría restringido a ser ≥5\geq 5 y ≤7\leq 7. Veamos qué pasaría si agregáramos otra actualización a esta secuencia:

add(5)\texttt{add(5)}, remove(7)\texttt{remove(7)}, remove(4)\texttt{remove(4)}

Ahora, los valores del rango solo pueden ser iguales a 44, porque los valores eran mayores que 44 antes de las actualizaciones de rango. Podemos manejar todas las actualizaciones de la manera descrita arriba.

Ahora que tenemos una cota inferior y una cota superior concretas, queda el problema de averiguar el valor final. Recordemos que cada actualización add\texttt{add} y remove\texttt{remove} esencialmente impuso una cota superior y una cota inferior sobre los valores. Así, restringir los valores del rango a estar en el intervalo [a,b][a, b] es esencialmente lo mismo que realizar dos actualizaciones: add(a)\texttt{add(a)} y remove(b)\texttt{remove(b)}. Como resultado, el resultado final para un valor individual es la cota inferior del valor que puede tomar.

Implementación

Complejidad temporal: O((N+Q)log⁡N)\mathcal{O}((N + Q)\log{N})

#include <bits/stdc++.h>
using namespace std;
 
struct Update {
	int min_val = 0;
	int max_val = INT_MAX;
};
class Segtree {
	const int sz;
	vector<Update> t;
 
	void apply(int v, const Update &x) {
		t[v].min_val = max(t[v].min_val, x.min_val);
		t[v].max_val = max(t[v].max_val, t[v].min_val);
		t[v].max_val = min(t[v].max_val, x.max_val);
		t[v].min_val = min(t[v].min_val, t[v].max_val);
	}
 
	void push_down(int v) {
		apply(2 * v, t[v]);
		apply(2 * v + 1, t[v]);
		t[v] = Update();
	}
 
	void update(int v, int l, int r, int ql, int qr, const Update &x) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(v, x);
		} else {
			push_down(v);
			int m = (l + r) / 2;
			update(2 * v, l, m, ql, qr, x);
			update(2 * v + 1, m + 1, r, ql, qr, x);
		}
	}
 
	Update query(int v, int l, int r, int idx) {
		if (l == r) {
			return t[v];
		} else {
			push_down(v);
			int m = (l + r) / 2;
			return (idx <= m) ? query(2 * v, l, m, idx)
			                  : query(2 * v + 1, m + 1, r, idx);
		}
	}
 
  public:
	Segtree(int n) : sz(n), t(4 * n) {}
 
	void update(int ql, int qr, const Update &x) { update(1, 0, sz - 1, ql, qr, x); }
 
	Update get(int idx) { return query(1, 0, sz - 1, idx); }
};
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
               int final_height[]) {
	Segtree st(n);
	for (int i = 0; i < k; i++) {
		if (op[i] == 1) {
			st.update(left[i], right[i], {height[i], INT_MAX});
		} else {
			st.update(left[i], right[i], {0, height[i]});
		}
	}
	for (int i = 0; i < n; i++) { final_height[i] = st.get(i).min_val; }
}
Fundamentos