QED's Favorite Permutation

Explicación

Un valor puede cruzar el hueco entre la posición $k$ y la posición $k+1$ hacia la derecha si $s_k = R$ , y hacia la izquierda si $s_{k+1} = L$ . Mientras un hueco siga abierto, los valores pueden cruzarlo de un lado a otro en cualquiera de las dos direcciones, así que cualquier secuencia de intercambios a través de huecos abiertos se puede reordenar en cualquier otro orden sin cambiar qué valores terminan dónde. Entonces, el orden de los intercambios no importa: que un valor pueda moverse de una posición a otra depende solo de $s$ , y se reduce a chequear si el camino requerido está obstruido.

El hueco es intransitable solo cuando $s_k = L$ y $s_{k+1} = R$ , lo que definimos como un hueco malo. Los huecos malos parten el arreglo en intervalos maximales donde cada dos posiciones adyacentes se pueden intercambiar libremente, así que dentro de uno de esos intervalos los valores se pueden reordenar en cualquier orden.

Para cada valor $v$ , sea $pos$ su posición actual en $p$ . Para que $p$ quede ordenado, $v$ debe terminar en la posición $v$ , así que debe viajar de $pos$ a $v$ , cruzando cada hueco estrictamente entre $\min(pos, v)$ y $\max(pos, v)$ . Otra forma de decirlo es que $pos$ y $v$ deben estar en el mismo intervalo, es decir, que no hay huecos malos entre $pos$ y $v$ para todos los valores de $v$ .

El rango $[\min(pos,v), \max(pos,v)]$ de cada valor marca los huecos de los que depende. Construimos un arreglo de diferencias, sumando $1$ en $\min(pos,v)$ y restando $1$ en $\max(pos,v)$ para cada valor $v$ . Tras tomar sumas de prefijos, cualquier hueco con valor positivo es requerido por al menos un valor. Definimos esos huecos como huecos importantes. Un hueco importante no se puede ignorar, porque algún valor $v$ necesita cruzarlo para llegar a su posición deseada. Todos los demás huecos se pueden ignorar, sean malos o no.

Solo importan los huecos importantes, porque son los únicos que pueden impedir el ordenamiento. Mantenemos un contador, bad, de cuántos huecos importantes son actualmente malos, y la respuesta es YES cuando bad vale cero. Una consulta en el índice $i$ solo afecta al hueco $i-1$ y al hueco $i$ , ya que son los únicos dos huecos que involucran a $s_i$ , así que podemos actualizar bad de forma directa.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, q;
		cin >> n >> q;
		vector<int> p(n + 1), pos(n + 1);
		for (int i = 1; i <= n; i++) {
			cin >> p[i];
			pos[p[i]] = i;
		}
 
		string s;
		cin >> s;
		s = " " + s;  // indexamos s desde 1
 
		// d[k] cuenta cuántos valores requieren que el hueco k se mantenga bueno
		vector<int> d(n + 1);
		for (int v = 1; v <= n; v++) {
			int lo = min(v, pos[v]), hi = max(v, pos[v]);
			d[lo]++;
			d[hi]--;
		}
 
		for (int k = 1; k <= n - 1; k++) {
			d[k] += d[k - 1];  // d[k] > 0 significa que el hueco k es importante
		}
 
		auto is_bad = [&](int k) { return s[k] == 'L' && s[k + 1] == 'R'; };
 
		// bad = cantidad de huecos importantes que actualmente son malos
		int bad = 0;
		for (int k = 1; k <= n - 1; k++) {
			if (d[k] > 0 && is_bad(k)) { bad++; }
		}
 
		while (q--) {
			int i;
			cin >> i;
 
			// solo los huecos i-1 e i pueden cambiar su "maldad" cuando se invierte s[i]
			for (int k : {i - 1, i}) {
				if (k >= 1 && k <= n - 1 && d[k] > 0 && is_bad(k)) { bad--; }
			}
 
			s[i] = (s[i] == 'L') ? 'R' : 'L';
			for (int k : {i - 1, i}) {
				if (k >= 1 && k <= n - 1 && d[k] > 0 && is_bad(k)) { bad++; }
			}
 
			cout << (bad == 0 ? "YES" : "NO") << '\n';
		}
	}
}