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.

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] \ldots 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 link.

Una vez leídas las queries, hay que responderlas. Para esto, hay distintos problemas que requieren distintos métodos.

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 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 $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)$.

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";
	}
}

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 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 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.)

Describir solucion, nodo, como mergear

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));
}
 
 
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];
	}
}
 
 
int main(){
	string s;
	while(cin>>s){
		rmq.clear();
		arr.clear();
 
		int n=s.size();
		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;
	}
}