Find and Replace

Análisis oficial (C++, Java) 

Explicación

La solución de fuerza bruta es construir el string de forma directa. Usamos una estructura de datos de árbol, donde los nodos hoja representan el string actual. Para cada operación $(c, s)$, colgamos nodos nuevos que representan los caracteres de $s$ en todos los nodos hoja con valor $c$.

Sin embargo, como la longitud del string puede crecer más allá de $2^{100000}$ (p. ej. duplicando el string cada vez), construir el árbol de forma directa no es viable. La ineficiencia más problemática es que la mayoría de los subárboles son idénticos. En concreto, después de cada operación, todos los nodos hoja con el mismo carácter producirán subárboles equivalentes, así que podemos enlazarlos todos a un nodo común.

Con esta estructura de datos más optimizada, ya podemos imprimir el string. Definamos un proceso recursivo $\texttt{print}(u, l, r)$, que imprime la subcadena $[l, r]$ en el nodo $u$. Para cada hijo $v$, si su rango correspondiente dentro de $u$ se intersecta con $[l, r]$, recurrimos a $\texttt{print}(v, l', r')$. Cuando llegamos a un nodo hoja, imprimimos su carácter correspondiente.

Para analizar la complejidad temporal de nuestra función de impresión, podemos dividir las consultas de impresión en dos tipos:

1. Consultas de impresión donde $[l, r]$ no es el string entero de $u$.
2. Consultas de impresión donde $[l, r]$ es el string entero de $u$.

Si $N$ es el número de operaciones, entonces hay $\mathcal{O}(N)$ consultas del primer tipo. La razón es que solo un prefijo y un sufijo de las posiciones en $[l, r]$ no llenan de forma limpia el rango entero de un nodo, y esos rangos solo pueden bajar por la estructura de datos, que tiene $N$ nodos.

El segundo tipo de consulta es más delicado. Para que el número de consultas de tipo 2 se amortice, necesitamos que el número de consultas de impresión sea proporcional a la longitud del string. Sin embargo, como nuestra estructura actual permite cadenas, el número de nodos puede crecer mucho más que el número de nodos hoja.

Para remediarlo, comprimimos todas las cadenas, ya que las cadenas no afectan nuestra respuesta. Como cada nodo de nuestro árbol tiene o bien $0$ o bien más de $1$ hijo, el número total de consultas de impresión de tipo 2 es $\mathcal{O}(L)$, donde $L$ es la longitud de nuestro string.

Con estas optimizaciones, nuestro algoritmo corre a tiempo. La implementación de abajo usa punteros, pero usar arreglos e índices en lugar de punteros también es perfectamente válido. También procesamos las consultas al revés para facilitar la construcción de la estructura de datos.

Implementación

Complejidad temporal: $\mathcal{O}(M+L)$, donde $M$ es la suma de $|s|$ sobre todas las operaciones, y $L$ es la longitud de nuestro rango.

#include <bits/stdc++.h>
using ll = long long;
 
constexpr ll INF = 1e18;
 
struct node {
	char c;
	ll size;
	std::vector<node *> nxt;
 
	void print(ll l, ll r) {
		if (nxt.empty()) {
			std::cout << c;
			return;
		}
 
		ll nl = 0;
		for (node *sub : nxt) {
			ll nr = nl + sub->size - 1;
 
			// calculate the intersection of the ranges
			// if there's a valid intersection, recurse
			ll pl = std::max(l, nl);
			ll pr = std::min(r, nr);
			if (pl <= pr) sub->print(pl - nl, pr - nl);
 
			nl += sub->size;
			if (nl > INF) break;
		}
	}
};
 
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
 
	ll l, r;
	int n;
	std::cin >> l >> r >> n;
	l--, r--;
 
	std::vector<std::pair<char, std::string>> ops(n);
	for (auto &[c, s] : ops) std::cin >> c >> s;
 
	std::array<node *, 26> prev;
	for (char c = 'a'; c <= 'z'; c++) { prev[c - 'a'] = new node{c, 1}; }
 
	// process operations in reverse when constructing
	for (int i = n - 1; i >= 0; i--) {
		const auto &[c, s] = ops[i];
		node *cur = new node{c, 0};
		for (char j : s) {
			// attach previous nodes to our new node from this operation
			// make sure to clamp size to INF (1e18) for overflow
			cur->size += prev[j - 'a']->size;
			if (cur->size > INF) cur->size = INF;
			cur->nxt.push_back(prev[j - 'a']);
		}
 
		// if a chain is formed, we can throw away our new node
		// and redirect prev[c] to the next 'relevant' node
		if (s.size() == 1) {
			prev[c - 'a'] = (cur->nxt)[0];
		} else {
			prev[c - 'a'] = cur;
		}
	}
 
	// call print(l, r) for the root
	prev[0]->print(l, r);
}