Divide y vencerás - SRQ

Consultas sobre un arreglo estático

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Static Range Minimum Queries	Muy fácil		en el módulo

Dado un arreglo estático $A[1],A[2],\ldots,A[N]$ , se quieren responder consultas de la forma

A[l]\ominus A[l+1]\ominus \cdots \ominus A[r]

donde $\ominus$ denota una operación asociativa.

En un módulo anterior se mostró que podemos obtener consultas en tiempo $\mathcal{O}(1)$ con preprocesamiento en tiempo $\mathcal{O}(N\log N)$ cuando $\ominus$ denota min. Pero ¿cómo generalizamos a otras operaciones asociativas?

Podemos usar divide y vencerás para responder $Q$ consultas offline en tiempo $\mathcal{O}((N+Q)\log N)$ u online en $\mathcal{O}(N\log N+Q)$ .

Consultas offline

Supongamos que todas las consultas satisfacen $L\le l\le r\le R$ (inicialmente, $L=1$ y $R=N$ ). Haciendo $M=\left\lfloor \frac{L+R}{2}\right\rfloor$ , podemos calcular

lef[l]=A[l]\ominus A[l+1]\ominus \cdots \ominus A[M]

para todo $L\le l\le M$ y

rig[r]=A[M+1]\ominus A[M+2] \ominus \cdots\ominus A[r]

para cada $M< r\le R$ . Entonces la respuesta para todas las consultas que satisfacen $l\le M< r$ es simplemente $lef[l]\ominus rig[r]$ por la condición de asociatividad. Después de eso, recursamos de forma independiente sobre todos los intervalos de consulta completamente contenidos en $[L,M]$ y $[M+1,R]$ .

El código de abajo debería funcionar si min se reemplaza por cualquier operación asociativa.

Solución - RMQ


#include <bits/stdc++.h>
using namespace std;
 
static const int MAXN = 200000 + 5;
 
int n, q, A[MAXN], B[MAXN];
vector<int> x, ans;
int lef[MAXN], rig[MAXN];
 
void divi(int l, int r, vector<int> v) {
	if (v.size() == 0) return;
 
	if (l == r) {
		for (int _ : v) ans[_] = x[l];
		return;
	}
 
	int m = (l + r) / 2;
 
	lef[m] = x[m];
	for (int i = m - 1; i >= l; i--) lef[i] = min(x[i], lef[i + 1]);
 
	rig[m + 1] = x[m + 1];
	for (int i = m + 2; i < r + 1; i++) rig[i] = min(rig[i - 1], x[i]);
 
	vector<int> todo[2];
	for (int t : v) {
		int a = A[t], b = B[t];
		if (a <= m && m < b) {  // we can answer the query immediately
			ans[t] = min(min(lef[a], x[m]), rig[b]);
			continue;
		}
		// otherwise
		// either [a,b] is contained within [l,m]   -> it's placed into todo[0]
		// or     [a,b] is contained within [m+1,r] -> it's placed into todo[1]
		todo[a > m].push_back(t);
	}
 
	divi(l, m, todo[0]);
	divi(m + 1, r, todo[1]);
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	cin >> n >> q;
 
	x.resize(n);
	for (int i = 0; i < n; i++) cin >> x[i];
 
	for (int i = 0; i < q; i++) {
		cin >> A[i] >> B[i];
		A[i]--, B[i]--;
	}
 
	vector<int> query(q);
	iota(query.begin(), query.end(), 0);
 
	ans.resize(q);
 
	divi(0, n - 1, query);
 
	for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

Consultas online

Hacemos lo mismo que arriba, excepto que almacenamos todos los valores calculados de lef y rig en un arreglo 2D usando $\mathcal{O}(N\log N)$ de memoria, de forma similar a una tabla dispersa.

Recursos
Fuente	Recurso	Notas
Benq	RangeQuery	implementación

Solución - RMQ

En el código de abajo, dat cumple los roles que tanto lef como rig cumplen en la solución anterior. Sea comb(l,r) igual a $A[l]\ominus A[l+1]\ominus \cdots \ominus A[r]$ . Por ejemplo, si $n=20$ y solo consideramos los niveles $0$ y $1$ entonces obtenemos

dat[0][i]=comb(i,9) para i en [0,9]
dat[0][i]=comb(10,i) para i en [10,19]
dat[1][i]=comb(i,4) para i en [0,4]
dat[1][i]=comb(5,i) para i en [5,9]
dat[1][i]=comb(i,14) para i en [10,14]
dat[1][i]=comb(15,i) para i en [15,19]
mask[0..4]=0
mask[5..9]=2
mask[10..14]=1
mask[15..19]=3

Ejemplos de consultas:

Para consultar comb(0,16) primero contamos el número de ceros a la derecha en mask[0] XOR mask[16], que es 0. Así que nuestra respuesta es min(dat[0][0],dat[0][16]).
Para consultar comb(12,18) primero contamos el número de ceros a la derecha en mask[12] XOR mask[18], que es 1. Así que nuestra respuesta es min(dat[1][12],dat[1][18]).


#include <bits/stdc++.h>
using namespace std;
 
static const int MAXN = 200000 + 5;
 
int n, q;
vector<int> x, ans;
 
int dat[18][MAXN];  // 18 = ceil(log2(n))
int mask[MAXN];
 
void divi(int l, int r, int lev) {  // generate dat and mask
	if (l == r) return;
 
	int m = (l + r) / 2;
 
	dat[lev][m] = x[m];
	for (int i = m - 1; i >= l; i--) dat[lev][i] = min(x[i], dat[lev][i + 1]);
 
	dat[lev][m + 1] = x[m + 1];
	for (int i = m + 2; i <= r; i++) dat[lev][i] = min(dat[lev][i - 1], x[i]);
 
	for (int i = m + 1; i <= r; i++) mask[i] ^= (1 << lev);
 
	divi(l, m, lev + 1);
	divi(m + 1, r, lev + 1);
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	cin >> n >> q;
 
	x.resize(n);
	for (int i = 0; i < n; i++) cin >> x[i];
 
	divi(0, n - 1, 0);
 
	for (int i = 0; i < q; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
 
		if (a == b) {
			cout << x[a] << '\n';
		} else {  // find level where info is stored
			      // ctz gives number of trailing zeroes
			int bits = __builtin_ctz(mask[a] ^ mask[b]);
			cout << min(dat[bits][a], dat[bits][b]) << '\n';
		}
	}
 
	return 0;
}

Preprocesamiento más rápido

Una estructura de datos conocida como Árbol Sqrt (sqrt-tree) puede acelerar el tiempo de preprocesamiento y la memoria a $\mathcal{O}(N\log \log N)$ .

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
JOI	2014 - Secret	Fácil		Solución
CC	Product on Segment	Fácil		—
Baltic OI	2017 - Toll	Normal		Solución
DMOPC	Continued Fractions	Normal		—
NOI	Estelle's Supper Box	Normal	DP, Knapsack, D&C, SRQ	Solución
Platinum	Non-Decreasing Subsequences	Difícil	Matrix, D&C	—
CF	Destiny	Difícil		—