Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:problemas-con-queries:offline-vs-online [2018/05/04 06:51]
sebach creado
+++ algoritmos-oia:problemas-con-queries:offline-vs-online [2018/10/08 17:00] (actual)
santo
@@ Línea 7: / Línea 7: @@
-PROBLEMAS
+[[http://codeforces.com/problemset/problem/932/B|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$.
+[[http://codeforces.com/problemset/problem/276/C|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]+...+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.
-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), 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. FIXME link a i/o
+[[http://codeforces.com/problemset/problem/713/A|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.
+[[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]$.
+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.
@@ Línea 21: / Línea 30: @@
 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 algoritmo de Mo. FIXME link
+Un algoritmo conocido para estos casos es el [[algoritmos-oia/problemas-con-queries/algoritmo-de-mo|algoritmo de Mo]].
-El problema de arriba de ......... por ejemplo, puede resolverse con este algoritmo. Veámoslo.
+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.
-CODIGO
+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 $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-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 queries.cpp>
+#include<bits/stdc++.h>
+using namespace std;
+#define forn(i,n) for(int i=0;i<(int)(n); i++)
+#define forsn(i,s,n) for(int i=(s);i<(int)(n); i++)
+#define pb push_back
+int maxn=1000003;
+vector<int> ans(maxn);
+int main(){
+ forn(i, 10)ans[i]=i;
+ forsn(i, 10, maxn){
+ int pro=1;
+ int nc=i;
+ while(nc){
+ int l=nc%10;
+ if(l)pro*=l;
+ nc/=10;
+ }
+                // calculo g(i) dinamicamente usando que el producto de los digitos siempre es menor que el numero
+ ans[i]=ans[pro];
+ }
+ vector< vector<int> > cant;
+ vector<int> dec(10, 0);
+ cant.pb(dec); // para que si l=1, cant[l-1][k]=cant[0][k] de 0 para cualquier k
+ forsn(i, 1, maxn){
+ dec.clear();
+ forn(j, 10){
+ dec.pb(cant[i-1][j]);
+ }
+ dec[ans[i]]++;
+ cant.pb(dec);
+ }
+ int n;
+ cin>>n;
+ while(n--){
+ int l, r, k;
+ cin>>l>>r>>k;
+ cout<<cant[r][k]-cant[l-1][k]<<"\n";
+ }
+}
+</code>
 ==== 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.
+Hay problemas, en cambio, que pueden hacer variar nuestro escenario con las queries, como "Sonya and Queries".
-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.
+En estos casos, tendremos que resolver el problema con algo más elaborado que ordenando las queries al final o precalculando todo al principio como hicimos en el código de "Recursive Queries", ya que la respuesta dependerá de en qué momento se efectuó cada query.
+La estructura más útil y más usada para este tipo de problemas (y también para algunos offline) es el [[algoritmos-oia/estructuras/segment-tree|Segment Tree]].
+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
+<code cpp sereja-and-brackets.cpp>
+#include<bits/stdc++.h>
+using namespace std;
+#define forn(i,n) for(int i=0;i<(int)(n); i++)
+#define forsn(i,s,n) for(int i=(s);i<(int)(n); i++)
+#define pb push_back
+struct node{
+ int a,b,c;
+};
+vector<char> arr;
+vector<node> rmq;
+vector<int> cant;
+char NEUTRO='(';
+node oper(node x, node y){
+ int t=min(x.b, y.c);
+ node ret;
+ ret.a=x.a+y.a+t;
+ ret.b=x.b+y.b-t;
+ ret.c=x.c+y.c-t;
+ return ret;
+}
+node res(int nodo, int l, int r, int i, int j){
+ node n;
+ n.a=0;
+ n.b=0;
+ n.c=0;
+ if(j<=l || i>=r)return n;
+ if(i<=l && j>=r){
+ return rmq[nodo];
+ }
+ return oper(res(nodo*2, l, (l+r)/2, i, j), res(nodo*2+1, (l+r)/2, r, i, j));
+}
-Estructuras que pueden resultar útiles para este tipo de problemas son FIXME linkssss!
+void build(){
+ node vacio;
+ for(int i=0; i<2*(int)(arr.size()); i++){
+ rmq.push_back(vacio);
+ cant.push_back(0);
+ }
+ for(int i=(int)(arr.size()); i<2*(int)(arr.size()); i++){
+ node nuevo;
+ nuevo.a=0;
+ if(arr[i-(int)arr.size()]=='('){
+ nuevo.b=1;
+ nuevo.c=0;
+ }else{
+ nuevo.c=1;
+ nuevo.b=0;
+ }
+ rmq[i]=nuevo;
+ cant[i]=1;
+ }
+ for(int i=(int)arr.size()-1; i>=1; i--){
+ rmq[i]=oper(rmq[2*i], rmq[2*i+1]);
+ cant[i]=cant[2*i]+cant[2*i+1];
+ }
+}
-Por ejemplo, en el problema de .......... de arriba:
+int main(){
+ string s;
+ while(cin>>s){
+ rmq.clear();
+ arr.clear();
-Solución
+ int n=s.size();
-Código
+  forn(i, s.size()){
+ arr.pb(s[i]);
+ }
+ int p2=1;
+ while(p2<n)p2*=2;
+ while(p2>n){
+ arr.push_back(NEUTRO);
+ p2--;
+ }
+ int si=(int)arr.size();
+ build();
+ // get ans of range [a,b) : res(1,0,si,a,b) -> con a=0,...,n-1
+ int q;
+ cin>>q;
+ while(q--){
+ int a,b;
+ cin>>a>>b;
+ a--;
+ node an=res(1, 0, si, a, b);
+ cout<<2*an.a<<endl;
+ }
+ return 0;
+ }
+}
+</code>

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página