OIA-Wiki

Las queries son preguntas que hay que resolver. Un problema con muchas queries, requiere, dada una situación fijada generalmente, hallar un respuesta que concierne a una parte de ese escenario. Por ejemplo, dado un conjunto de números, una query puede consistir en preguntar cuántos números de un número dado hay. O un poco más difícil, dado un conjunto de intervalos, una query puede consistir en dado un número averiguar cuántos intervalos del conjunto lo contienen.

Ejemplos de problemas:

Recursive Queries: $g(n)$ es el resultado de multiplicar los dígitos de $n$ distintos de $0$, hasta tener un número de $1$ cifra. Te dan $Q\leq 2*10^5$ queries, con $l,r\leq 10^6 ,k<10$. Hay que decir cuántos enteros $l \leq x \leq r$ existen tales que $g(x)=k$.

Maxima suma de queries: Tenés un array $a$ de $n \leq 10^5$ enteros, y te van a dar $q \leq 10^5$ queries, con dos números $1 \leq l_i \leq r_i \leq n$, y te piden la suma de $a[l_i]+a[l_i+1]+\ldots+a[r_i]$. Vas a tener que acomodar el array al principio, para que la suma total de los resultados de la query sea máxima.

Sonya and Queries: Te van dando queries de agregar y sacar números, y cada tanto te preguntan cuántos números tenés actualmente que matcheen con un patrón dado.

Con las queries, hay que tener cuidado con cuántas hay. Si hay muchas queries (del orden de $10^5 van a ser en general, más no porque hay que leer cada una, es decir no podrías ni siquiera leer$10^9l$y$r$hay. Puedo guardar información de cuántos hay entre$1$y$x$para todo$x$, y luego responder "cuántos hay entre$1$y$r$menos cuántos hay entre$1$y$l-1k$es chico, puedo guardar en$cuantos[i][k]$cuántos$x$hay entre$1$e$i$cuya función$g(x)=k$. Tomaría del orden de$O(10*N)$completar los estados, y luego respondo las queries en$O(1)$.

CODIGO

Hay problemas, en cambio, que pueden hacer variar nuestro escenario con las queries. Por ejemplo, puede haber dos tipos de query, uno que nos pida una respuesta a alguna pregunta, y otra que modifique algo, por ejemplo que agregue un número a un conjunto, o lo elimine. En estos casos, tendremos que resolver el problema con algo más elaborado que ordenando las queries al final, ya que la respuesta dependerá de en qué momento se efectuó cada query.

Estructuras que pueden resultar útiles para este tipo de problemas son linkssss!

Por ejemplo, en el problema de .......... de arriba:

Solución Código