Borrado offline

Usando una estructura de datos persistente o rollback, se puede simular el borrado de una estructura de datos usando solo operaciones de inserción.

DSU con rollback

DSU con rollback es una extensión de DSU que guarda las uniones y puede deshacer las $k$ uniones anteriores.

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	YS	Persistent Union Find	Fácil	DSUrb	Solución
	MMCC	Inaho	Fácil	DSUrb	Solución

Implementación

Agregando al DSU usual, podemos guardar el padre y los tamaños de los nodos que se están uniendo antes de cada unión. Esto nos permite revertir cada nodo a sus padres antes de la unión para que la función de rollback pueda usar la información para deshacer las uniones.

Podemos guardar cada estado del DSU usando un entero, capturado por la función snapshot que devuelve el número de uniones viejas que no se han revertido. Es similar a tomar una foto de algo, y años después volver al álbum de fotos y desplazarse hacia arriba hasta encontrar esta foto.

Por ejemplo, si el arreglo de historia guarda $\{(1, 2), (3, 4), (1, 3)\}$ , esto significa que antes de nuestra unión más reciente, el elemento representante de la componente $3$ es $1$ , y antes de eso el elemento representante de la componente $4$ es $3$ . Si queremos revertir dos uniones, sacaríamos los últimos dos elementos del arreglo de historia y actualizaríamos los elementos representantes en orden.

¡Además, podemos extender este arreglo para revertir tamaños de componentes o cualquier otra cosa que nuestro DSU pueda rastrear!

C++Python


class DSU {
  private:
	vector<int> p, sz;
	// stores previous unites
	vector<pair<int &, int>> history;
 
  public:
	DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
 
	int get(int x) { return x == p[x] ? x : get(p[x]); }
 
	void unite(int a, int b) {
		a = get(a);
		b = get(b);
		if (a == b) { return; }
		if (sz[a] < sz[b]) { swap(a, b); }
 
		// save this unite operation
		history.push_back({sz[a], sz[a]});
		history.push_back({p[b], p[b]});
 
		p[b] = a;
		sz[a] += sz[b];
	}
 
	int snapshot() { return history.size(); }
 
	void rollback(int until) {
		while (snapshot() > until) {
			history.back().first = history.back().second;
			history.pop_back();
		}
	}
};


class DSU:
	def __init__(self, n: int):
		self.p = list(range(n))
		self.sz = [1] * n
		self.history = []  # stores all history info related to merges
 
	def get(self, x) -> int:
		if self.p[x] == x:
			return x
		return self.get(self.p[x])
 
	def unite(self, a: int, b: int):
		a = self.get(a)
		b = self.get(b)
		if a == b:
			return
		if self.sz[a] < self.sz[b]:
			a, b = b, a
 
		# add to history
		self.history.append((self.p, b, self.p[b]))
		self.history.append((self.sz, a, self.sz[a]))
 
		self.p[b] = a
		self.sz[a] += self.sz[b]
 
	def snapshot(self) -> int:
		return len(self.history)
 
	def rollback(self, until: int):
		while self.snapshot() > until:
			arr, idx, val = self.history.pop()
			arr[idx] = val

Conectividad dinámica

Conectividad dinámica (Dynamic Connectivity) es el problema más común que usa el truco de borrar. Estos tipos de problemas involucran determinar si pares de nodos están en la misma componente conexa mientras se insertan y quitan aristas.

Recursos
Fuente	Recurso	Notas
CP-Algorithms	Deleting from a data structure in O(T(n) log n)
GCP	15.5.4 - Dynamic Connectivity
CF	Dynamic Connectivity Contest
Vivek Gupta	Dynamic Connectivity Video Explanation

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	YS	Vertex Add Component Sum	Normal	Dynacon	en el módulo

Solución - Vertex Add Component Sum

Para problemas de conectividad dinámica, decimos que para cada consulta hay un intervalo $[l, r]$ donde está activa. Obviamente, para cada consulta de agregar/quitar arista, $l =$ (el índice de la consulta que agrega la arista), y $r =$ (el índice de la consulta que quita la arista) $-1$ . Si una arista nunca se quita, entonces $r = q - 1$ . Observar que asignamos intervalos de modo que para consultas fuera del intervalo, no se ven afectadas en absoluto por esta consulta. Podemos usar un razonamiento similar para construir intervalos para consultas de tipo $2$ y $3$ .

Ahora podemos construir un árbol de consultas. Si nuestro intervalo está encapsulado por el intervalo del árbol, entonces podemos agregar nuestra consulta al nodo correspondiente al intervalo. Al responder consultas, al entrar en el intervalo, podemos procesar todas las operaciones dentro del intervalo. Al salir del intervalo, necesitamos deshacerlas. Si estamos en una hoja, podemos responder consultas de tipo $3$ ya que hemos procesado todas las consultas fuera de este intervalo $[i, i]$ . Como estamos procesando intervalos por mitades cada vez, la profundidad es a lo sumo $\log n$ , similar a divide y vencerás.

Ver el código de abajo para detalles de implementación. ¡Observar que, similar a las operaciones unite, también podemos realizar y deshacer operaciones de tipo $2$ !

C++Python


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
// BeginCodeSnip{DSU}
class DSU {
  private:
	vector<ll> p, sz, sum;
	// stores all history info related to merges
	vector<pair<ll &, ll>> history;
 
  public:
	DSU(int n) : p(n), sz(n, 1), sum(n) { iota(p.begin(), p.end(), 0); }
 
	void init_sum(const vector<ll> a) {
		for (int i = 0; i < (int)a.size(); i++) { sum[i] = a[i]; }
	}
 
	int get(int x) { return (p[x] == x) ? x : get(p[x]); }
 
	ll get_sum(int x) { return sum[get(x)]; }
 
	void unite(int a, int b) {
		a = get(a);
		b = get(b);
		if (a == b) { return; }
		if (sz[a] < sz[b]) { swap(a, b); }
 
		// add to history
		history.push_back({p[b], p[b]});
		history.push_back({sz[a], sz[a]});
		history.push_back({sum[a], sum[a]});
 
		p[b] = a;
		sz[a] += sz[b];
		sum[a] += sum[b];
	}
 
	void add(int x, ll v) {
		x = get(x);
		history.push_back({sum[x], sum[x]});
		sum[x] += v;
	}
 
	int snapshot() { return history.size(); }
 
	void rollback(int until) {
		while (snapshot() > until) {
			history.back().first = history.back().second;
			history.pop_back();
		}
	}
};
// EndCodeSnip
 
const int MAXN = 3e5;
 
DSU dsu(MAXN);
 
struct Query {
	int t, u, v, x;
};
 
vector<Query> tree[MAXN * 4];
 
void update(Query &q, int v, int query_l, int query_r, int tree_l, int tree_r) {
	if (query_l > tree_r || query_r < tree_l) { return; }
	if (query_l <= tree_l && query_r >= tree_r) {
		tree[v].push_back(q);
		return;
	}
	int m = (tree_l + tree_r) / 2;
	update(q, v * 2, query_l, query_r, tree_l, m);
	update(q, v * 2 + 1, query_l, query_r, m + 1, tree_r);
}
 
void dfs(int v, int l, int r, vector<ll> &ans) {
	int snapshot = dsu.snapshot();
	// perform all available operations upon entering
	for (Query &q : tree[v]) {
		if (q.t == 1) { dsu.unite(q.u, q.v); }
		if (q.t == 2) { dsu.add(q.v, q.x); }
	}
	if (l == r) {
		// answer type 3 query if we have one
		for (Query &q : tree[v]) {
			if (q.t == 3) { ans[l] = dsu.get_sum(q.v); }
		}
	} else {
		// go deeper into the tree
		int m = (l + r) / 2;
		dfs(2 * v, l, m, ans);
		dfs(2 * v + 1, m + 1, r, ans);
	}
	// undo operations upon exiting
	dsu.rollback(snapshot);
}
 
int main() {
	int n, q;
	cin >> n >> q;
	vector<ll> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }
	dsu.init_sum(a);
 
	map<pair<int, int>, int> index_added;
	for (int i = 0; i < q; i++) {
		int t;
		cin >> t;
		if (t == 0) {
			int u, v;
			cin >> u >> v;
			if (u > v) swap(u, v);
			// store index this edge is added, marks beginning of interval
			index_added[{u, v}] = i;
		} else if (t == 1) {
			int u, v;
			cin >> u >> v;
			if (u > v) swap(u, v);
			Query cur_q = {1, u, v};
			// add all edges that are deleted to interval [index added, i - 1]
			update(cur_q, 1, index_added[{u, v}], i - 1, 0, q - 1);
			index_added[{u, v}] = -1;
		} else if (t == 2) {
			int v, x;
			cin >> v >> x;
			Query cur_q = {2, -1, v, x};
			// add all sum queries to interval [i, q - 1]
			update(cur_q, 1, i, q - 1, 0, q - 1);
		} else if (t == 3) {
			int v;
			cin >> v;
			Query cur_q = {3, -1, v};
			// add all output queries to interval [i, i]
			update(cur_q, 1, i, i, 0, q - 1);
		}
	}
 
	// add all edges that are not deleted to interval [index added, q - 1]
	for (auto [edge, index] : index_added) {
		if (index != -1) {
			Query cur_q = {1, edge.first, edge.second};
			update(cur_q, 1, index, q - 1, 0, q - 1);
		}
	}
 
	vector<ll> ans(q, -1);
	dfs(1, 0, q - 1, ans);
	for (int i = 0; i < q; i++) {
		if (ans[i] != -1) { cout << ans[i] << "\n"; }
	}
}


MAXN = 300000
tree = [[] for _ in range(4 * MAXN)]
 
# BeginCodeSnip{DSU}
class DSU:
	def __init__(self, n: int):
		self.p = list(range(n))
		self.sz = [1] * n
		self.sum = [0] * n
		self.history = []  # stores all history info related to merges
 
	def init_sum(self, a: list[int]):
		for i in range(len(a)):
			self.sum[i] = a[i]
 
	def get(self, x) -> int:
		if self.p[x] == x:
			return x
		return self.get(self.p[x])
 
	def get_sum(self, x: int) -> int:
		return self.sum[self.get(x)]
 
	def unite(self, a: int, b: int):
		a = self.get(a)
		b = self.get(b)
		if a == b:
			return
		if self.sz[a] < self.sz[b]:
			a, b = b, a
 
		# add to history
		self.history.append((self.p, b, self.p[b]))
		self.history.append((self.sz, a, self.sz[a]))
		self.history.append((self.sum, a, self.sum[a]))
 
		self.p[b] = a
		self.sz[a] += self.sz[b]
		self.sum[a] += self.sum[b]
 
	def add(self, x: int, v: int):
		x = self.get(x)
		self.history.append((self.sum, x, self.sum[x]))
		self.sum[x] += v
 
	def snapshot(self) -> int:
		return len(self.history)
 
	def rollback(self, until: int):
		while self.snapshot() > until:
			arr, idx, val = self.history.pop()
			arr[idx] = val
 
 
# EndCodeSnip
 
 
class Query:
	def __init__(self, t: int, u: int, v=None, x=None):
		self.t = t
		self.u = u
		self.v = v
		self.x = x
 
 
dsu = DSU(MAXN)
 
 
def update(q: Query, v: int, query_l: int, query_r: int, tree_l: int, tree_r: int):
	if query_l > tree_r or query_r < tree_l:
		return
	if query_l <= tree_l and query_r >= tree_r:
		tree[v].append(q)
		return
	m = (tree_l + tree_r) // 2
	update(q, 2 * v, query_l, query_r, tree_l, m)
	update(q, 2 * v + 1, query_l, query_r, m + 1, tree_r)
 
 
def dfs(v: int, l: int, r: int, ans: list[int]):
	snapshot = dsu.snapshot()
	for q in tree[v]:
		if q.t == 1:
			dsu.unite(q.u, q.v)
		elif q.t == 2:
			dsu.add(q.v, q.x)
	if l == r:
		for q in tree[v]:
			if q.t == 3:
				ans[l] = dsu.get_sum(q.v)
	else:
		m = (l + r) // 2
		dfs(2 * v, l, m, ans)
		dfs(2 * v + 1, m + 1, r, ans)
	dsu.rollback(snapshot)
 
 
n, q = map(int, input().split())
a = list(map(int, input().split()))
dsu.init_sum(a)
index_added = {}
ans = [-1] * q
 
for i in range(q):
	query = list(map(int, input().split()))
	t = query[0]
	if t == 0:
		u, v = query[1:]
		if u > v:
			u, v = v, u
		# store index this edge is added, marks beginning of interval
		index_added[(u, v)] = i
	elif t == 1:
		u, v = query[1:]
		if u > v:
			u, v = v, u
		cur_q = Query(1, u, v)
 
		# add all edges that are deleted to interval [index added, i - 1]
		update(cur_q, 1, index_added[(u, v)], i - 1, 0, q - 1)
		index_added[(u, v)] = -1
	elif t == 2:
		v, x = query[1:]
		cur_q = Query(2, -1, v, x)
 
		# add all sum queries to interval [i, q - 1]
		update(cur_q, 1, i, q - 1, 0, q - 1)
	elif t == 3:
		v = query[1]
		cur_q = Query(3, -1, v)
 
		# add all output queries to interval [i, i]
		update(cur_q, 1, i, i, 0, q - 1)
 
# add all edges that are not deleted to interval [index added, q - 1]
for (edge, index) in index_added.items():
	if index != -1:
		cur_q = Query(1, edge[0], edge[1])
		update(cur_q, 1, index, q - 1, 0, q - 1)
 
dfs(1, 0, q - 1, ans)
for res in ans:
	if res != -1:
		print(res)

Fuente	Nombre	Dificultad	Tags	Solución
CF	Connect and Disconnect	Fácil	Dynacon	—
CF	Envy	Normal	DSUrb	Solución
CF	★ Disconnected Graph	Normal	DSUrb	—
CF	Extending Set of Points	Normal	DSUrb	—
CF	Forced Online Queries Problem	Difícil	Dynacon	—
CF	A Museum Robbery	Difícil	Dynacon	—
Baltic OI	2020 - Joker	Muy difícil	D&C, DSUrb	—