Making Friends on Joitter is Fun

El problema pide el número máximo de follows después de cada evento de intercambio social, pero ¿es siquiera posible no alcanzar ese máximo?

Consideremos el siguiente escenario: hay $X$ personas numeradas de $1$ a $X$, y para cada $2 \leq i \leq X$, las personas $i$ e $i - 1$ se siguen mutuamente. ¿Cómo quedarán sus follows después de un evento de intercambio social?

Siguiendo la pista 2, ¿qué pasa si hay otras $Y$ personas numeradas de $X + 1$ a $X + Y$, y la persona $1$ sigue a la persona $X + 1$ mientras que la persona $X + Y$ sigue a la persona $X$?

Estamos tratando con una estructura tipo DSU, así que la fusión small-to-large puede ser útil.

Complejidad temporal: $\mathcal O(M \log^2 N)$.

Siempre terminaremos con el mismo número de follows después de un evento de intercambio social, independientemente del orden en que elijamos las ternas $(x, y, z)$.

Consideremos el siguiente grafo:

• Los nodos representan personas en Joitter.
• Hay dos tipos de aristas: rojas y azules.
  • Las aristas rojas son no dirigidas y representan un follow mutuo
  • Las aristas azules son dirigidas y representan un follow unidireccional

La observación clave es que si el nodo $u$ puede alcanzar el nodo $v$ usando solo aristas rojas, entonces quedarán conectados con una arista roja después de un evento de intercambio social. Esto sugiere que deberíamos usar DSU para llevar las componentes de nodos conectados por aristas rojas.

Además, si tenemos dos componentes separadas $A$ y $B$, cuatro nodos $u_A, v_A \in A, u_B, v_B \in B$ (no necesariamente distintos), y las aristas azules $u_A \rightarrow v_B$ y $u_B \rightarrow v_A$, entonces cada par de nodos en $A \cup B$ también tendrá una arista roja entre ellos después de un evento de intercambio social. Esto significa que deberíamos fusionar $A$ y $B$ en el DSU si esto ocurre.

Podemos usar fusión small-to-large para llevar las aristas azules entre componentes en tiempo $\mathcal O(M \log^2 N)$.

(Nótese que fusionar dos componentes puede hacer que otras componentes también se fusionen, así que también hay que mantener una cola de qué componentes hay que fusionar.)

Aunque tenemos una estructura agradable para guardar y fusionar componentes, todavía hay que calcular el cambio en la respuesta cada vez que dos componentes $A$ y $B$ se fusionan.

Sea $V_i$ el número de follows después de la $i$-ésima fusión, y sea $F_S$ el conjunto de personas fuera de la componente $S$ que siguen a alguien en $S$.

1. Hay que restar el número de follows dentro de las $A$ y $B$ previamente no fusionadas. Como cada par de personas se seguía mutuamente, este número es $|A| \cdot (|A| - 1) + |B| \cdot (|B| - 1)$.
2. Hay que sumar el número de follows dentro de la $A \cup B$ recién fusionada. Como cada par de personas se seguirá mutuamente, este número es $|A \cup B| \cdot (|A \cup B| - 1)$.
3. Hay que sumar el número de follows fuera de $A \cup B$. Como las personas que antes seguían a todos en $A$ ahora también seguirán a todos en $B$ y viceversa, este número es $|A| \cdot |F_B| + |B| \cdot |F_A|$.
4. Hay que restar el número de follows de las personas que ya seguían a todos en $A$ y $B$ o que ya estaban en $A$ o $B$. Este número es $|(A \cup F_A) \cap (B \cup F_B)| \cdot |A \cup B|$.

Juntando todo y definiendo $C_S = S \cup F_S$, obtenemos:

Podemos usar fusión small-to-large de nuevo para llevar cada $C_S$ en tiempo $\mathcal O(M \log^2 N)$.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
int cmp[100001];
ll sz[100001], ans = 0;
set<int> child[100001], graph[100001], rgraph[100001];
queue<pair<int, int>> to_merge;
 
void insert_weak_connection(int A, int B) {
	graph[A].insert(B);
	rgraph[B].insert(A);
	// If there's A new strong connection between A's and B's components, merge
	// them
	if (graph[B].count(A)) to_merge.push({A, B});
}
 
int dsu_size(int A) { return child[A].size() + graph[A].size() + rgraph[A].size(); }
 
int find(int A) { return (A == cmp[A] ? A : cmp[A] = find(cmp[A])); }
 
void onion(int A, int B) {
	if (A == B) return;
	// Merge the smaller component into the larger
	if (dsu_size(A) < dsu_size(B)) swap(A, B);
 
	// Add new contribution
	ans += sz[B] * child[A].size() + sz[A] * child[B].size();
 
	// DSU stuff
	cmp[B] = A;
	sz[A] += sz[B];
 
	// Merge children of B into A
	for (int i : child[B]) {
		if (child[A].count(i)) ans -= sz[A];
		else child[A].insert(i);
	}
	// Erase the connections
	graph[A].erase(B), rgraph[A].erase(B);
	graph[B].erase(A), rgraph[B].erase(A);
	// Merge the weak connections to other components
	for (int i : graph[B]) {
		rgraph[i].erase(B);
		insert_weak_connection(A, i);
	}
	for (int i : rgraph[B]) {
		graph[i].erase(B);
		insert_weak_connection(i, A);
	}
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cmp[i] = i;
		sz[i] = 1;
		child[i].insert(i);
	}
	while (m--) {
		int A, B;
		cin >> A >> B;
 
		B = find(B);
		// If A isn't in B's component and doesn't already follow someone in B's
		// component...
		if (find(A) != B && !child[B].count(A)) {
			// We insert A as A follower of B and add sz[find(B)] to the answer
			child[B].insert(A);
			ans += sz[B];
 
			A = find(A);
			// Add connections between components
			insert_weak_connection(A, B);
			// We may have to merge multiple components for each new event
			while (to_merge.size()) {
				tie(A, B) = to_merge.front();
				to_merge.pop();
				onion(find(A), find(B));
			}
		}
		cout << ans << '\n';
	}
	return 0;
}