Skip to Content
CTRL K

Substring Reversals

Explicación

Hay que aplicar m reversiones. Un enfoque de fuerza bruta lleva a O(N∗M)\mathcal{O}(N * M). Por lo tanto no es viable. En su lugar, podemos usar un Treap implícito junto con propagación perezosa.

¿Qué es lo implícito en este Treap?

En un treap normal, cada nodo guarda una clave explícita que determina su posición en el orden del BST. En un treap implícito no hay una clave almacenada para el orden: la posición de cada elemento se calcula de forma implícita usando los tamaños de los subárboles.

El recorrido inorden (DFS) representa la secuencia actual, y el índice de cualquier nodo queda determinado por cuántos nodos hay en su subárbol izquierdo. Esto permite partir y fusionar por posición de forma eficiente sin mantener ni actualizar índices explícitos (después de aplicar operaciones de reversión).

Para revertir una subcadena del índice LL al RR, hacemos los siguientes pasos:

  1. Aislar la subcadena: Usamos la función split para dividir el Treap en tres árboles separados: T1 (elementos antes del índice LL), T2 (elementos de LL a RR) y T3 (elementos después del índice RR).
  2. Reversión perezosa: Revertir físicamente cada nodo de T2 sería demasiado lento. En su lugar usamos un bool, rev. Simplemente conmutamos este flag en la raíz de T2.
  3. Reensamblar: Usamos la función merge para volver a unir T1, T2 y T3.

Cada vez que recorremos el árbol (durante split, merge, print), llamamos a la función push sobre el nodo actual. Si el flag rev está activo, push intercambia físicamente los punteros a los hijos izquierdo y derecho del nodo y pasa el flag rev a sus hijos. Así se retrasa el trabajo real hasta que un nodo tiene que ser accedido de verdad.

Por último, un dfs empuja hacia abajo todas las actualizaciones perezosas restantes e imprime el string final.

Implementación

Complejidad temporal: O((N+M)log⁡N)\mathcal{O}((N + M) \log N)

#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Implicit Treap template}
struct ImplicitTreap {
	struct Node {
		char val;
		int prior, sz;
		bool rev;
		Node *l, *r;
		Node(char v, int p) : val(v), prior(p), sz(1), rev(0), l(nullptr), r(nullptr) {}
	};
 
	using pNode = Node *;
	mt19937 rng{chrono::steady_clock::now().time_since_epoch().count()};
	pNode root = nullptr;
 
	int sz(pNode t) { return t ? t->sz : 0; }
 
	void pull(pNode t) {
		if (t) t->sz = 1 + sz(t->l) + sz(t->r);
	}
 
	void push(pNode t) {
		if (!t || !t->rev) return;
		swap(t->l, t->r);
		if (t->l) t->l->rev ^= 1;
		if (t->r) t->r->rev ^= 1;
		t->rev = 0;
	}
 
	void split(pNode t, pNode &l, pNode &r, int k) {
		if (!t) {
			l = r = nullptr;
			return;
		}
		push(t);
		if (sz(t->l) >= k) {
			split(t->l, l, t->l, k);
			r = t;
		} else {
			split(t->r, t->r, r, k - sz(t->l) - 1);
			l = t;
		}
		pull(t);
	}
 
	pNode merge(pNode l, pNode r) {
		if (!l || !r) return l ? l : r;
		if (l->prior > r->prior) {
			push(l);
			l->r = merge(l->r, r);
			pull(l);
			return l;
		} else {
			push(r);
			r->l = merge(l, r->l);
			pull(r);
			return r;
		}
	}
 
	void build(const string &s) {
		for (char c : s) root = merge(root, new Node(c, rng()));
	}
 
	void reverse(int l, int r) {
		pNode t1, t2, t3;
		split(root, t1, t2, l - 1);
		split(t2, t2, t3, r - l + 1);
		if (t2) t2->rev ^= 1;
		root = merge(t1, merge(t2, t3));
	}
 
	void dfs(pNode t) {
		if (!t) return;
		push(t);
		dfs(t->l);
		cout << t->val;
		dfs(t->r);
	}
 
	void print() { dfs(root); }
};
// EndCodeSnip
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n, m, l, r;
	string s;
	cin >> n >> m >> s;
 
	ImplicitTreap treap;
	treap.build(s);
 
	while (m--) {
		cin >> l >> r;
		treap.reverse(l, r);
	}
 
	treap.print();
}
Fundamentos