Matryoshka

Explicación

Primero, consideremos una sola consulta: ¿cuál es la cantidad mínima de muñecas que quedan? Una sola muñeca anidada consiste en algunas muñecas de $R_i$ y $H_i$ crecientes. Si ordenamos las muñecas por $H_i$ y solo consideramos sus $R_i$, entonces la respuesta es la cantidad mínima de subsecuencias crecientes necesarias para “cubrir” todas las muñecas.

Es bien sabido que la cantidad mínima de subsecuencias crecientes es igual a la subsecuencia no creciente más larga (ver el módulo de LIS para más detalles). ¡Esto nos da una forma de responder una sola consulta en tiempo $\mathcal O(N \log N)$!

¿Pero qué pasa si necesitamos responder múltiples consultas?

Como no tenemos que responder las consultas online, ordenémoslas en orden decreciente de $A_i$. Si $B_i = \infty$ para cada consulta, entonces simplemente podemos hacer una línea de barrido sobre las muñecas y las consultas, insertando muñecas en la secuencia y actualizando la subsecuencia no creciente más larga a medida que llegamos a ellas.

Para $B_i$ variables, solo queremos la subsecuencia no creciente más larga para algunos prefijos de la secuencia de muñecas (no la secuencia entera como antes). Así, podemos hacer búsqueda binaria sobre el arreglo de DP de hallar la subsecuencia no creciente más larga para encontrar esta respuesta. Esto se debe a que el arreglo de DP guarda, para cada $l$, la muñeca con el $R_j$ más pequeño con una subsecuencia no creciente que termina en ella con longitud $l$.

Implementación

Complejidad temporal: $\mathcal O((N + Q) \log N)$

#include <bits/stdc++.h>
using namespace std;
 
pair<int, int> doll[200000];
pair<pair<int, int>, int> query[200000];
int ans[200000];
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, q;
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> doll[i].first >> doll[i].second;
		doll[i].second = -doll[i].second;
	}
	for (int i = 0; i < q; i++) {
		cin >> query[i].first.first >> query[i].first.second;
		query[i].second = i;
	}
	sort(doll, doll + n, greater<pair<int, int>>());
	sort(query, query + q, greater<pair<pair<int, int>, int>>());
 
	vector<pair<int, int>> dp;
	for (int i = 0, j = 0; i < q; i++) {
		while (j < n && doll[j].first >= query[i].first.first) {
			int lds =
			    upper_bound(dp.begin(), dp.end(), make_pair(-doll[j].second, INT_MAX)) -
			    dp.begin();
			if (lds == dp.size()) dp.push_back({-doll[j].second, doll[j].first});
			else dp[lds] = {-doll[j].second, doll[j].first};
			j++;
		}
		ans[query[i].second] = upper_bound(dp.begin(), dp.end(),
		                                   make_pair(query[i].first.second, INT_MAX)) -
		                       dp.begin();
	}
 
	for (int i = 0; i < q; i++) cout << ans[i] << '\n';
	return 0;
}