Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
algoritmos-oia:problemas-con-queries:offline-vs-online [2018/05/07 14:26] sebach |
algoritmos-oia:problemas-con-queries:offline-vs-online [2018/10/08 17:00] (actual) santo |
||
---|---|---|---|
Línea 37: | Línea 37: | ||
Como $k$ 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)$. | Como $k$ 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)$. | ||
- | <code cpp union-find.cpp> | + | <code cpp queries.cpp> |
#include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
Línea 91: | Línea 91: | ||
Por ejemplo, el problema "Sereja and Brackets" de arriba, vamos a resolverlo con Segment Tree. (Leer primero ese post para entender la solución.) | Por ejemplo, el problema "Sereja and Brackets" de arriba, vamos a resolverlo con Segment Tree. (Leer primero ese post para entender la solución.) | ||
+ | |||
+ | FIXME Describir solucion, nodo, como mergear | ||