Lynyrd Skynyrd

Pista 1

Para cada posición en el arreglo $a$ , calcular el índice del siguiente valor necesario en la permutación.

Pista 2

Para cada extremo izquierdo, calcular el extremo derecho mínimo de un rango que tenga una subsecuencia adecuada.

Solución

Como se mencionó en las pistas, calculamos el índice del siguiente valor necesario en la permutación. Con esta información, podemos guardar un arreglo $lift[x][y]$ , que almacena el índice mínimo para tener cubiertos $2^{x}$ valores de nuestra permutación, si empezamos en el índice $y$ del arreglo $a$ .

Después de precalcular nuestros binary lifts, usamos binary lifting para calcular el extremo derecho mínimo de un desplazamiento cíclico de nuestra permutación para cada extremo izquierdo. Para calcular la mejor respuesta en el rango $[l, r]$ , o bien usamos RMQ o bien guardamos los mínimos de prefijo/sufijo de las respuestas.

Implementación

Complejidad temporal: $\mathcal{O}(N\log{N})$

C++


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	int m;
	int q;
	cin >> n >> m >> q;
	vector<int> p(n);
	vector<int> p_index(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i];
		p_index[--p[i]] = i;
	}
 
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
		a[i]--;
	}
 
	const int log_n = 1 + (int)log2(n);
	vector<vector<int>> lift(log_n, vector<int>(m + 1, m));
	vector<int> last_occ(n, m);
	for (int i = m - 1; i >= 0; i--) {
		int nxt = p[(p_index[a[i]] + 1) % n];
		lift[0][i] = last_occ[nxt];
		last_occ[a[i]] = i;
		for (int j = 1; j < log_n; j++) { lift[j][i] = lift[j - 1][lift[j - 1][i]]; }
	}
 
	vector<int> res(m + 1, m);
	for (int i = m - 1; i >= 0; i--) {
		int cur_idx = i;
		for (int j = log_n - 1; j >= 0; j--) {
			if (((n - 1) >> j) & 1) { cur_idx = lift[j][cur_idx]; }
		}
		res[i] = min(cur_idx, res[i + 1]);
	}
 
	for (int i = 0; i < q; i++) {
		int l, r;
		cin >> l >> r;
		cout << (res[l - 1] < r);
	}
}