Consulta de máximo en sufijo solo con inserciones

Nota: esto estaba originalmente en Oro, pero los problemas de práctica eran demasiado difíciles…

Para resolver este problema, necesitamos una estructura de datos que soporte operaciones similares a las siguientes:

1. Agregar un par $(a,b)$.
2. Para cualquier $x$, consultar el valor máximo de $b$ entre todos los pares que cumplen $a\ge x$.

Esto se puede resolver con un Árbol de Segmentos, pero una opción más simple es usar un mapa. Nos apoyamos en el hecho de que si existen pares $(a,b)$ y $(c,d)$ en el mapa tales que $a\le c$ y $b\le d$, podemos ignorar $(a,b)$ (y las respuestas a consultas futuras no se verán afectadas). Así, en todo momento, los pares $(a_1,b_1),(a_2,b_2),\ldots,(a_k,b_k)$ que guardamos en el mapa cumplirán $a_1 < a_2 < \cdots < a_k$ y $b_1 > b_2 > \cdots > b_k$.

• Consultar un cierto $x$ se puede hacer con una sola operación lower_bound, ya que solo queremos el mínimo $i$ tal que $a_i\ge x$.
• Al agregar un par $(a',b')$, primero comprobamos si ya existe $(a,b)$ en el mapa tal que $a\ge a', b\ge b'$.
  • Si es así, no hacemos nada.
  • En caso contrario, insertamos $(a',b')$ en el mapa y borramos repetidamente pares $(a,b)$ tales que $a\le a', b\le b'$ hasta que no quede ninguno.

Si hay $N$ inserciones, cada consulta toma $\mathcal{O}(\log N)$ y agregar un par toma $\mathcal{O}(\log N)$ amortizado.

Implementación

#define lb lower_bound
 
map<int, ll> m;
void ins(int a, ll b) {
	auto it = m.lb(a);
	if (it != end(m) && it->s >= b) return;
	it = m.insert(it, {a, b});
	it->s = b;
	while (it != begin(m) && prev(it)->s <= b) m.erase(prev(it));
}
ll query(int x) {
	auto it = m.lb(x);
	return it == end(m) ? 0 : it->s;
}
// it = end(m) means that no pair satisfies a >= x

Se puede consultar el análisis  para la solución completa del problema original.

Problemas