Skip to Content
CTRL K

The Best Subsequence

Análisis oficial (C++) 

Pista 1

Supongamos que tenemos alguna función caja negra que cuenta el número de unos en el rango [l,r][l, r]. Consideremos dos casos: uno en el que el número de unos en nuestro rango es menor que KK, y si el número de unos es mayor o igual que KK. ¿Cómo podemos manejar estos dos casos?

Pista 2

Si el número de unos es ≥K\geq K, entonces nuestra subsecuencia puede consistir de solo unos. En caso contrario, necesitamos dejar entrar cierta cantidad de ceros a nuestra subsecuencia.

Digamos que el número de unos en nuestro rango es XX. Entonces, necesitamos dejar entrar K−XK-X ceros a nuestro rango, y queremos que el primer cero venga lo más atrás posible. ¿A qué corresponde esto en nuestro arreglo?

Solución

Como se denota en las pistas, sea XX el número de unos en nuestro rango.

Caso 1: X≥KX \geq K

Toda nuestra subsecuencia son unos, así que la respuesta es 2k−12^k - 1.

Caso 2: X<KX < K

Siempre es óptimo tomar el sufijo más pequeño de [l,r][l, r] que tiene K−XK - X ceros. Para entender esto de forma intuitiva, consideremos el hecho de que queremos maximizar la primera posición en la que tenemos un cero en nuestra subsecuencia. Dado que necesitamos tomar al menos K−XK-X ceros, es óptimo tomar los últimos K−XK-X ceros de nuestro rango. Como estamos intentando maximizar la subsecuencia resultante, también es óptimo tomar los unos dentro del sufijo que terminamos tomando. Nótese que hay otras formas de maximizar la primera posición de un cero.

Calcular el resultado

Para calcular 2k2^k de forma eficiente, usamos exponenciación modular. Esto nos permite manejar el caso 1 con bastante facilidad.

Como se mencionó en las pistas, queremos alguna función para hallar de forma eficiente el número de unos en un rango dado. Primero simplifiquemos este problema a contar el número de unos en un prefijo. Podemos hacerlo comprimiendo coordenadas de nuestros valores, y luego calculando sumas de prefijos del número de unos en nuestro prefijo. Aquí se requiere una implementación cuidadosa, ya que hay que asegurarse de que el último intervalo de nuestra suma de prefijos no se sobrecuente.

Podemos reducir el problema de calcular el hash de un rango a hallar el hash de un prefijo. Para cada intervalo, guardamos el hash de todo el prefijo que incluye este intervalo. Hay que manejar con cuidado los intervalos que están parcialmente contenidos en nuestro prefijo. Entonces, el hash de [l,r][l, r] es:

\texttt{pref\\_hash}(r) - 2^{r - l + 1} \cdot \texttt{pref\\_hash}(l - 1)

Para elegir el sufijo de nuestro rango que hasheamos, necesitamos hallar el sufijo más pequeño que tiene K−XK - X ceros. Esto es equivalente a hallar el último índice mm donde el número de ceros en [m,r][m, r] es ≥K−X\geq K-X. La forma más fácil de implementar esto es con búsqueda binaria, aunque es posible recortar un factor logarítmico hallando el intervalo en el que está nuestro índice mm usando lower bound sobre una suma de prefijos de ceros.

Implementación

Complejidad temporal: O(Qlog⁡2N+Mlog⁡M+Mlog⁡N)\mathcal{O}(Q\log^2N + M\log M + M\log N)

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
constexpr int MOD = 1e9 + 7;
 
/** @return base^exp mod 1e9 + 7 */
int modpow(int base, int exp) {
	int res = 1;
	for (; exp; exp /= 2, base = (1ll * base * base) % MOD) {
		if (exp & 1) { res = (1ll * res * base) % MOD; }
	}
	return res;
}
 
int main() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> vals = {0, INT_MAX};
	vector<array<int, 2>> upds(m);
	for (auto &[l, r] : upds) {
		cin >> l >> r;
		r++;
		vals.push_back(l);
		vals.push_back(r);
	}
 
	// comprimimos coordenadas de todos los valores relevantes
	sort(begin(vals), end(vals));
	vals.erase(unique(begin(vals), end(vals)), end(vals));
 
	/** @return valor con coordenadas comprimidas de x */
	const auto id = [&](int x) -> int {
		return lower_bound(begin(vals), end(vals), x) - begin(vals);
	};
 
	const int range_len = vals.size();
	vector<int> diff(range_len);
	for (const auto &[l, r] : upds) {
		diff[id(l)]++;
		diff[id(r)]--;
	}
 
	// pref[i] = número de 1s en los primeros i intervalos
	vector<int> pref(range_len);
	for (int i = 0; i + 1 < range_len; i++) {
		diff[i + 1] += diff[i];
		diff[i] &= 1;
		pref[i + 1] = pref[i] + diff[i] * (vals[i + 1] - vals[i]);
	}
 
	// pref_hash[i] = hash del valor de los primeros i intervalos del arreglo
	vector<int> pref_hash(range_len);
	for (int i = 0; i + 1 < range_len; i++) {
		const int len = vals[i + 1] - vals[i];
		const int pw2 = modpow(2, len);
		pref_hash[i + 1] =
		    diff[i] * (pw2 - 1 + MOD) % MOD + (1ll * pref_hash[i] * pw2) % MOD;
		pref_hash[i + 1] %= MOD;
	}
 
	/** @return el valor del rango [l, r] */
	const auto range_hash = [&](int l, int r) -> int {
		const auto get_pref = [&](int x) -> int {
			// podemos usar nuestro hash de prefijo, pero x puede estar a mitad de un intervalo
			// así que partimos la respuesta en el hash de prefijo y un intervalo más chico
			const int pos = upper_bound(begin(vals), end(vals), x) - begin(vals) - 1;
			const int pw2 = modpow(2, x - vals[pos] + 1);
			return (1ll * pref_hash[pos] * pw2 + diff[pos] * (pw2 - 1)) % MOD;
		};
 
		// para obtener el hash de rango a partir de hashes de prefijo, hay que
		// desplazar el hash de prefijo de [0, l - 1] para que restarlo funcione
		ll raw = get_pref(r) - 1ll * modpow(2, r - l + 1) * get_pref(l - 1);
		return (raw % MOD + MOD) % MOD;
	};
 
	/** @return el número de 1s en el rango [l, r] */
	const auto get_ones = [&](int l, int r) -> int {
		const auto get_pref = [&](int x) -> int {
			// podemos usar nuestro hash de prefijo, pero x puede estar a mitad de un intervalo
			// así que partimos la respuesta en el valor de suma de prefijos y un intervalo más chico
			const int pos = upper_bound(begin(vals), end(vals), x) - begin(vals);
			return pref[pos - 1] + diff[pos - 1] * (x - vals[pos - 1] + 1);
		};
 
		return get_pref(r) - get_pref(l - 1);
	};
 
	for (int t = 0; t < q; t++) {
		int l, r, k;
		cin >> l >> r >> k;
		const int num_ones = get_ones(l, r);
		if (num_ones >= k) {
			cout << modpow(2, k) - 1 << "\n";
		} else {
			// búsqueda binaria para hallar el sufijo más pequeño con k - num_ones ceros
			int lo = l, hi = r;
			while (lo < hi) {
				int mid = (lo + hi + 1) / 2;
				bool works = (r - mid + 1) - get_ones(mid, r) >= k - num_ones;
				works ? lo = mid : hi = mid - 1;
			}
 
			const int suffix_hash = range_hash(lo, r);
			const int suffix_ones = get_ones(lo, r);
			const ll res =
			    suffix_hash + modpow(2, k) - modpow(2, k - (num_ones - suffix_ones));
			cout << (res % MOD + MOD) % MOD << "\n";
		}
	}
}
Fundamentos