Skip to Content
CTRL K

2011 - Tree Rotations

Análisis oficial (polaco) 

Explicación

El número de inversiones que resulta de unir dos conjuntos es la suma de las inversiones dentro de los dos conjuntos más el número de inversiones nuevas después de unir los dos conjuntos, donde cada inversión nueva tiene un elemento en el conjunto izquierdo y otro en el derecho. Así, para contar la mejor forma de fusionar los dos conjuntos, necesitamos hallar las inversiones si intercambiamos o no intercambiamos los dos conjuntos.

La implementación de abajo usa fusión small-to-large y conjuntos ordenados para contar de forma eficiente las menores inversiones que podemos tener al combinar los conjuntos de nuestros subárboles izquierdo y derecho. Iteramos sobre el conjunto más pequeño, y usamos el método order_of_key del conjunto ordenado para contar el número de elementos <x< x y >x> x, para cada valor de hoja xx dentro del conjunto más pequeño.

Implementación

Complejidad temporal: O(Nlog⁡2N)\mathcal{O}(N\log^2N)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
int main() {
	int n;
	cin >> n;
 
	int timer = 0;
	vector<ll> inversions(2 * n - 1);
	map<int, Tree<int>> sets;
	function<void(int)> dfs = [&](int idx) {
		int val;
		cin >> val;
 
		if (val == 0) {
			int idx_l = ++timer;
			dfs(idx_l);
			int idx_r = ++timer;
			dfs(idx_r);
 
			if (sets[idx_l].size() > sets[idx_r].size()) {
				sets[idx_l].swap(sets[idx_r]);
			}
 
			ll way_1 = 0;  // way 1: left set is joined to the right set
			ll way_2 = 0;  // way 2: right set is joined to the left set
			for (int v : sets[idx_l]) {
				int loc = sets[idx_r].order_of_key(v);
				way_1 += loc;
				way_2 += (int)sets[idx_r].size() - loc;
			}
 
			for (int v : sets[idx_l]) { sets[idx_r].insert(v); }
			sets[idx].swap(sets[idx_r]);
			sets.erase(idx_l);
			sets.erase(idx_r);
 
			inversions[idx] = inversions[idx_l] + inversions[idx_r] + min(way_1, way_2);
		} else if (val > 0) {
			sets[idx].insert(val);
		}
	};
 
	dfs(0);
 
	cout << inversions[0] << endl;
}
Fundamentos