Herramientas de usuario
algoritmos-oia:problemas-con-queries:offline-vs-online
Diferencias
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:25] sebach |
algoritmos-oia:problemas-con-queries:offline-vs-online [2018/10/08 17:00] (actual) santo |
||
|---|---|---|---|
| Línea 16: | Línea 16: | ||
| - | [[http://codeforces.com/contest/381/problem/E|Sereja and Brackets]](difícil): Te dan una string $s$ de paréntesis y te dan varias queries, que consisten en dos enteros $l, r$. Hay que responder la máxima longitud de una subsecuencia bien parenteseada de la substring $s[l]s[l+1]\.\.\.s[r]$. | + | [[http://codeforces.com/contest/381/problem/E|Sereja and Brackets]](difícil): Te dan una string $s$ de paréntesis y te dan varias queries, que consisten en dos enteros $l, r$. Hay que responder la máxima longitud de una subsecuencia bien parenteseada de la substring $s[l]s[l+1] ... s[r]$. |
| 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 63: | Línea 63: | ||
| vector< vector<int> > cant; | vector< vector<int> > cant; | ||
| vector<int> dec(10, 0); | vector<int> dec(10, 0); | ||
| - | cant.pb(dec); | + | cant.pb(dec); // para que si l=1, cant[l-1][k]=cant[0][k] de 0 para cualquier k |
| forsn(i, 1, maxn){ | forsn(i, 1, maxn){ | ||
| dec.clear(); | dec.clear(); | ||
| 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 | ||
algoritmos-oia/problemas-con-queries/offline-vs-online.1525703128.txt.gz · Última modificación: 2018/05/07 14:25 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
