Herramientas de usuario
¡Esta es una revisión vieja del documento!
Qué son las queries
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^9![$ queries), y las queries consisten de varios números, o palabras, hay que tener mucho cuidado con el método de input/output utilizado. Habrá que usar el método más rápido posible para que esto no sea un problema. Para eso pueden leer este [[algoritmos-oia/input-output|link]].
Una vez leídas las queries, hay que responderlas.
Para esto, hay distintos problemas que requieren distintos métodos.
==== Queries offline ====
Son queries, que pueden responderse al final, todas juntas. Esto es en general en un escenario que no va cambiando con el tiempo (es decir con el avance de las queries).
Si es el escenario está siempre fijo, no importa cuándo nos den una query, ni cuándo la respondamos, la respuesta siempre será la misma.
Aprovechando esto, podremos por ejemplo, al recibir todas las queries, ordenarlas, y en base a eso elaborar un algoritmo eficiente que resuelva el problema con las queries ordenadas.
Un algoritmo conocido para estos casos es el [[algoritmos-oia/problemas-con-queries/algoritmo-de-mo|algoritmo de Mo]].
El problema de arriba de "Recursive Queries" es un ejemplo de queries Offline, mientras que "Sonya and Queries" no, porque te van cambiando el escenario y en el medio te hacen preguntas sobre el estado actual.
Acá dejo el código de "Recursive Queries", sin ningún algoritmo loco. Simplemente, una idea copada también para estas queries es, me piden cuántos números entre $](/lib/plugins/latex/images/renderfail.png "Fail: triggered security filter; contains blacklisted LaTeX tags.")
l$ 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
Queries online
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
Herramientas de la página
