Introducción
A veces, puede ser interesante la idea de separar en cosas grandes y pequeñas para poder mejorar un algoritmo. Veamos el siguiente problema: Quieres saber cuántos múltiplos de $X$ hay entre $A$ y $B$ que no tengan ningún dígito $7$. Supongamos que $1 \leq A, B \leq 10^{12}$. Si $X$ es pequeño, tiene demasiados múltiplos en el peor caso, por lo que no podemos comprobarlos uno a uno. Podremos hacer una DP de estado DP[modulo X][posición digito] que tiene coste de memoria $\mathcal{O}(X \log X)$, pero esto es demasiado grande para $X > 10^5$. Nos fijamos entonces que si $X > 10^5$, sí que podemos simplemente pasar por todos los múltiplos ya que habrá $(B-A)/X < 10^7$ de estos. Por lo que tenemos una solución que resuelve casos pequeños de una manera y casos grandes de otra, de forma eficiente.
Blocking
Vamos a hablar de una idea que permite resolver problemas principalmente de llevar a cabo operaciones sobre una lista de elementos. Vamos a usar como motivación el siguiente problema: Tenemos una lista de $N$ enteros, y nos harán $Q$ consultas en las que nos pueden pedir calcular la suma de un rango y también modificar el valor en una posición. Si lo hacemos de forma directa, simplemente calculando las sumas cada vez, tendremos una solución $\mathcal{O}(NQ)$. Si no hubiera modificaciones podríamos usar la técnica de sumas de prefijos, pero al haber modificaciones volvería a ser $\mathcal{O}(NQ)$.
La idea de Sqrt decomposition es agrupar los elementos de nuestra lista por bloques, y calcular cosas dentro del bloque de manera que si una consulta de rango contiene todos los elementos de un bloque no tengamos que recalcularlo. Vamos a suponer que hacemos bloques de $S$ elementos, entonces tendremos $\lceil N/S \rceil$ (redondeado hacia arriba) bloques en total. ¿Cómo usamos los bloques de manera que podamos mejorar nuestra solución? Pues por ejemplo en este caso podemos mantener la suma de un bloque entero. Si lo modificamos recalculamos la suma del bloque en $O(1)$ sumando la diferencia. ¿Cuánto tarda una consulta ahora? Hay un bloque cada $S$ elementos, por lo que nuestro rango puede tener por la derecha y por la izquiera como máximo $S-1$ elementos fuera de los bloques totalmente contenidos, y luego tenemos como mucho $N/S$ bloques, por lo que tenemos que sumar $\mathcal{O}(S+N/S)$ valores en cada consulta.
Vamos a escoger $S$ de forma que se minimice este coste. Podemos ver que el mínimo de la función $f(x) = x + \frac{N}{x}$ se obtiene con $x = \sqrt{N}$. Por tanto, $S = \sqrt{N}$ será el valor óptimo, dándonos un coste $\mathcal{O}(\sqrt{N})$ por consulta (de aquí en nombre Sqrt decompisition) y por tanto $\mathcal{O}(Q\sqrt{N})$ en total. Es importante resaltar que este método es online, es decir, no necesitamos conocer todas las consultas de antemano y podemos responder una consulta antes de tener la siguiente. Con $N=Q=10^6$ las anteriores soluciones habrían tardado más de una hora, mientras que ahora tan solo unos segundos. Así sería el problema implementado:
#include <bits/stdc++.h>
using namespace std;
// Es importante que S y B sean constantes para que el compilador optimice:
const int N = 2e5; // tamaño máximo del array
const int S = (int)sqrt(N); // tamaño de los bloques
const int B = N/S + 1; // máximo número de bloques
// Usamos arrays porque no necesitamos cambiar el tamaño y serán un poco más eficientes:
int arr[N];
long long block[B]; // guardará la suma de cada bloque
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
// calculamos la suma de los bloques. El elemento i va al bloque i/S
fill(block, block+B, 0);
for (int i = 0; i < n; ++i) {
block[i/S] += arr[i];
}
for (int j = 0; j < q; ++j) {
int t; // tipo de consulta
cin >> t;
if (t == 1) {
int k, u; // arr[k] actualizado al valor u
cin >> k >> u;
--k; // pasamos a 0-indexed
// update O(1)
block[k/S] += u - arr[k];
arr[k] = u;
}
else {
int a, b; // suma en [a, b]
cin >> a >> b;
--a; --b; // pasamos a 0-indexed
// range sum O(sqrt N)
long long sum = 0;
int i = a;
while (i <= b) {
// Si se cumple esto podemos sumar el bloque entero y saltar
if (i%S == 0 and i+S < b) {
sum += block[i/S];
i += S;
}
else {
sum += arr[i];
++i;
}
}
cout << sum << endl;
}
}
}
Esta forma de agrupar datos es de las más versátiles, podríamos cambiar a problemas como mínimo de rango, o modifical valores también en un rango. En casos más complejos tendremos bloques más complicados que usen otras estructuras internamente, como un std::set, por ejemplo. En estos casos, tenemos que contar cuánto tardan las diversas operaciones y buscar el tamaño de bloque idóneo, que normalmente seguirá siendo cercano a $\sqrt{N}$. Un consejo en la práctica es probar tamaños de bloque más grandes o más pequeños, ya que en los cálculos no consideramos el factor constante y tal vez multiplicando o dividiendo por $2$ nuestro tamaño funcione mejor en la práctica.
Modificaciones lazy
Imaginemos que en el problema anterior nos piden modificar todos los valores de un rango. No queremos modificarlos realmente de golpe porque entonces sería una operación $\mathcal{O}(N)$. Lo que haremos es modificar solo los valores que queden en los extremos del rango fuera de bloques enteros, que son como mucho $\mathcal{O}(S)$, y en los bloques modificar la suma a $(\text{num. elementos})\cdot(\text{nuevo valor})$, pero con un nuevo dato en el bloque, que nos indique que tenemos pendiente modificar todos los valores del array en las posiciones que corresponden a este bloque. Si más adelante una consulta de suma de rango necesita pasar por una parte de los valores del bloque, haremos entonces la modificación, ya que cada consulta solo puede tocar dos bloques de forma incompleta y por tanto será $\mathcal{O}(S)$. Se conoce como lazy ya que no hace las modificaciones cuando se le piden sino solo cuando es estrictamente necesario para poder calcular alguna otra consulta futura (de manera "perezosa"). Con todo esto vemos que mantenemos el coste $\mathcal{O}(Q\sqrt{N})$.
Batching
En ocasiones puede ser dificil poder modificar de manera eficiente, en este caso podemos aplicar una idea de Sqrt decomposition de manera diferente: En lugar de hacerlo a los datos, podemos hacerlo con las consultas. En lugar de aplicar las consultas de modificar, las iremos guardando hasta que tengamos muchas. Cuando haya muchas las aplicaremos todas de golpe. Por otra parte cuando nos pidan calcular algo sobre nuestros datos, tendremos que adaptarlo para que tenga en cuenta las modificaciones que tenemos guardadas pero no aplicadas.
Usaremos el siguiente problema como motivación: Tenemos un tablero de $N \times M$ casillas pintadas inicialmente de blanco. Nos pueden pedir que pintemos una casilla blanca de negro, o que digamos cuál es la distancia a la casilla negra más cercana. Si primero tuviéramos que pintar y luego responder, haríamos un multi-BFS desde todas las casillas negras y guardaríamos las distancias en las casillas blancas, lo que tendría un coste $\mathcal{O}(NM)$ por el multi-BFS inicial y luego las $Q$ consultas en $\mathcal{O}(1)$ hacen un coste total de $\mathcal{O}(NM + Q)$. Pero este no es el caso, las consultas pueden venir en cualquier orden, intercalando consultas de pintar y de calcular distancia. Haremos lo siguiente: Iremos guardando casillas que debemos pintar sin hacerlo realmente. Cuando nos pregunten la casilla negra más cercana usaremos la respuesta precalculada, y además miraremos también una a una las (menos de $S$) que hemos guardado ya que deberían ser negras también, viendo si reducen la distancia. Cuando el tamaño de las guardadas supere $S$, entonces pintaremos todas y recalcularemos de nuevo la solución para todas las casillas con el multi-BFS. Definiendo $K=NM$, el coste total es: $\mathcal{O}(QS + KQ/S)$. Resulta que el óptimo vuelve a ser coger $S=\sqrt{K}$ y entonces el coste total es $\mathcal{O}(Q \sqrt{K}) = \mathcal{O}(Q \sqrt{NM})$
Algoritmo de Mo
Supongamos que tenemos un problema de consultas en un rango, pero que no es sencillo calcular las respuestas a las consultas ya que la única forma es ir añadiendo o eliminando elementos uno a uno de alguna estructura de datos hasta que tengamos exactamente los de nuestro rango y podamos calcular la solución. En estas condiciones no podremos resolverlo eficientemente de manera online, ya que pueden hacernos añadir y eliminar la mitad de elementos en cada consulta. Un ejemplo de problema online nos obligaría a usar la respuesta de una consulta para la siguiente. Estamos estancados en una solución $\mathcal{O}(QN \ T(N))$, donde $T(N)$ es el coste de añadir o eliminar cada elemento si tenemos $\mathcal{O}(N)$ elementos ya añadidos. Pero, ¿y si no necesitamos hacerlo online? En ese caso sería un problema offline, en el que tenemos todas las consultas antes de dar las respuestas. Si además tenemos un problema (o lo adaptamos) en el que las consultas son independientes (no modificamos valores para futuras consultas), podemos utilizar una idea de Sqrt decomposition para resolver las consultas más rápido.
Vamos a usar el siguiente problema como motivación: Tenemos una lista con $N$ valores $a_i$, y tenemos $Q$ consultas $(L_i, R_i)$ que nos piden calcular lo siguiente: Para cada valor que aparece en el rango, sumamos el valor por el número de veces que aparece este valor al cuadrado. Es decir, si el valor $s$ aparece $K_s$ veces, sumamos $s \cdot K_s^2$. ¿Cómo lo resolvemos eficientemente? Observamos que es fácil añadir o quitar un elemento, lo que hacemos es tener un array con los valores $K_s$, inicialmente todo a $0$. Si añadimos un elemento $x$, restamos $x \cdot K_x^2$ a la solución actual, sumamos $1$ a $K_x$ y sumamos $x \cdot K_x^2$ a la solución actual. La resta se hace de manera similar. Ahora nos falta ordenar las consultas en un buen orden, de manera que para pasar de una a otra añadiendo y quitando elementos no hagamos demasiadas operaciones. Lo que haremos es lo siguiente: tendremos un intervalo $[L, R]$ actual en el que tenemos la solución calculada y lo iremos moviendo, añadiendo y eleminando elementos. Agruparemos por bloques las consultas respecto a $L_i$, y dentro de un mismo bloque ordenadas por $R_i$ crecientemente. Es decir, si tenemos bloques de tamaño $S$, usamos como orden la tupla $(L_i/S, R_i)$. Nos fijamos que cada consulta varía la izquierda como mucho $S$ posiciones por cada una de las $Q$ consultas, excepto cuando cambiamos de bloque, que puede ser que pase por $\mathcal{O}(N)$ elementos, pero eso solo puede pasar $N/S$ veces. La $R$ puede variar lo que quiera, pero siempre será creciente entre las consultas de un mismo bloque, por lo que cada bloque se puede añadir por la parte derecha el array entero una sola vez. Como hay $Q/S$ bloques, el coste total es: $\mathcal{O}((N \ N/S + QS) \ T(N))$, que cogiendo $S=\sqrt{N}$ nos queda en total $\mathcal{O}((N+Q) \sqrt{N} \ T(N))$.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
const int N = 200000+1;
const int Q = 200000+1;
const int A = 1e6+1;
const int S = (int)sqrt(N);
struct Query {
int l, r, idx;
pair<int,int> ord;
Query() {}
Query(int l_, int r_, int i_) {
l = l_; r = r_; idx = i_;
ord = {l/S, r};
}
bool operator<(const Query& rhs) {
return ord < rhs.ord;
}
};
int l, r;
int a[N];
ll out[Q];
...
void add(int i) { ... }
void rem(int i) { ... }
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, t;
cin >> n >> t;
for (int i = 0; i < n; ++i) cin >> a[i];
vector<Query> qs(t);
for (int i = 0; i < t; ++i) {
int ql, qr;
cin >> ql >> qr;
--ql; --qr; // pasamos a 0-indexed
qs[i] = Query(ql, qr, i);
}
sort(qs.begin(), qs.end());
add(0);
ans = l = r = 0; // rango y solución actuales
for (auto& q : qs) {
// Cada vez que pasamos a otra consulta quitamos/añadimos
// elementos de uno en uno hasta que coincida con el rango
while (r > q.r) rem(r--);
while (r < q.r) add(++r);
while (l < q.l) rem(l++);
while (l > q.l) add(--l);
out[q.idx] = ans;
}
for (int i = 0; i < t; ++i) {
cout << out[i] << '\n';
}
}
Mejorar el orden de las consultas
Resulta que si alternamos en los bloques el orden creciente/decreciente de $R_i$, reducimos el número de cálculos necesarios ya que aprovechamos la posición en la que nos hemos quedado en el anterior bloque. Esto lo haríamos cambiando ord = {l/S, r} por ord = {l/S, r*(l/S % 2 ? -1 : +1)}. Si queremos ir más allá, (esto no será necesario en olimpiadas, pero es interesante), vemos que el coste de añadir o eliminar es $T(N)$, tras procesar la i-esima consulta hacemos $|L_i - L_{i+1}| + |R_i - R_{i+1}|$ operaciones, y el coste total serà $\mathcal{O}(T(N) \ \sum_i (|L_i - L_{i+1}| + |R_i - R_{i+1}|))$ para el orden elegido de las consultas. Minimizar esto es un caso del problema del viajante. Este problema es NP-completo y no se conocen soluciones no exponenciales, pero resulta que una buena aproximación inicial se puede conseguir usando curvas que recubren el plano. Podemos usar la curva de Hilbert para ordenar nuestras consultas respecto a qué orden las visitaría la curva, considerandolas como los puntos $(L_i, R_i)$. Con esta idea conseguimos un muy buen orden que nos garantiza un coste $O(N\sqrt{Q} \ T(N))$, lo que nos beneficia siempre, y aún más cuando $Q<N$. Para más detalles y cómo calcular la posición en la curva: https://codeforces.com/blog/entry/61203
Square Root Tree
Sqrt-tree es una estructura de datos que nos permite resolver queries de rango en $O$(1), con una precomputación en $O$($n$$log$$log$($n$)), siendo la mejor estructura de datos conocida para resolver problemas de queries en rango sobre vectores estáticos, observad que $log_2$($log_2$($10^6$)) $<$ 5, por lo que es muy útil incluso para "colar" soluciones a problemas con una complejidad esperada de $O$($n$).
El funcionamiento es el siguiente:
Digamos que tenemos una operación asociativa (es decir: $a$ $\circ$ ($b$ $\circ$ $c$) = ($a$ $\circ$ $b$) $\circ$ $c$), y queremos construir una estructura de datos que nos permita calcular el valor de realizar esta operación en un rango [$L$, $R$] en el vector $a$, es decir, calcular $a_L$ $\circ$ $a_{L+1}$ $\circ$ ... $\circ$ $a_R$.
Un primer intento de resolver este problema puede ser agrupar $a$ en bloques de tamaño $\sqrt n$, para calcular los prefijos y sufijos de cada bloque, de forma que si el bloque $i$-ésimo empieza en la posición $s$ y acaba en la posición $t$, tengamos precomputadas todas las queries [$s$, $k$] y [$k$, $t$] para todo $k$ $\in$ [$s$, $t$], observad que calcular esto para todos los bloques tiene coste $O$($\sqrt n^2$) = $O$($n$). También nos interesa para cada pareja de bloques $i$, $j$, precomputar el coste de todo el rango entre ellos.
De esta forma, podemos responder a todas las queries donde los límites se encuentran en bloques diferentes en $O$(1), tomando un sufijo del bloque en el que comienza, un rango de bloques, y un prefijo del bloque en el que acaba.
¿Pero, cómo podemos resolver las queries que se encuentran contenidas en un solo bloque? La respuesta es simple, repetimos el proceso recursivamente en cada bloque hasta tener bloques de tamaño 1 o 2. Obteniendo un árbol de profundidad $O$($log$$log$$n$).
Demostración: Si tenemos un vector tamaño $k$, sus hijos tendran tamaño $\sqrt k$ y ya que $log \sqrt k$ = $\frac{1}{2} log k$, la sucesión $k$, $\sqrt k$, ..., no solo decrece logarítmicamente, sino que el logaritmo también decrece logarítmicamente.
Ahora mismo tenemos una estructura de datos con una complejidad de precomputado de $O$($n$$log$$log$$n$) y coste de $O$($log$$log$$n$), si realizamos una búsqueda binaria podemos mirar en qué profundidad del árbol consultar nuestra query en $O$($log$$log$$log$$n$). Pero podemos saber que profundidad del árbol consultar de una forma incluso más fácil de implementar.
Lo primero de todo es que extenderemos la longitud de los bloques a potencias de dos, esto nos permitirá calcular eficientemente en que profundidad consultar nuestra query [$L$, $R$], ya que solo tendremos que fijarnos en cuál es el primer bit en el que difieren $L$ y $R$ (esto podemos calcularlo realizando $L$ $Xor$ $R$ y usar la función __builtin_clz()).
Más información (y como realizar updates) en: Sqrt-tree.
Añadir nuevo comentario