Bubblesort

Intuición

En este problema, hay que hallar la máxima disminución en el número de inversiones del arreglo.

En primer lugar, a menos que el arreglo ya esté ordenado, siempre podemos disminuir el número de inversiones. También podemos asumir que solo intercambiamos $a_i$ y $a_j$ ( $i < j$ ) si $a_i > a_j$ . (¿Se podría demostrar esto formalmente?)

Después de experimentar con algunos intercambios y arreglos, vemos que los únicos elementos del arreglo que contribuyen a ese cambio si intercambiamos $a_i$ y $a_j$ ( $i < j$ ) son los $a_k$ tales que $i \leq k \leq j$ y $a_i \geq a_k \geq a_j$ .

Esta condición se parece a las desigualdades que definen un rectángulo. ¿Podríamos encontrar una interpretación geométrica de este problema?

Convertir el problema en geometría

Graficamos los puntos $(i, a_i)$ en el plano cartesiano.

Nótese que si intercambiamos $a_i$ y $a_j$ ( $i < j$ ), el cambio en el número de inversiones es igual a:

(\text{No. of points strictly inside the rectangle }(i, a_i, j, a_j)) + (\text{No. of points in or on the rectangle }(i, a_i, j, a_j)) - 1

A partir de esto, también vemos que si tenemos $x < y$ y $a_x \geq a_y$ , entonces $y$ no puede ser el índice izquierdo en el intercambio óptimo.

Esto significa que podemos considerar simplemente un conjunto de $i$ con $a_i$ estrictamente creciente como candidatos para el índice izquierdo en el intercambio óptimo.

Usar la optimización D&C

Sea $opt_i$ el índice tal que, si debemos intercambiar $a_i$ con algo a su derecha, entonces intercambiarlo con $a_{opt_i}$ es óptimo.

Como $a_i$ es estrictamente creciente en nuestro conjunto de candidatos, podemos demostrar que $opt_i \geq opt_{i - 1}$ para todo $i$ de nuestro conjunto.

Esto significa que podemos usar la optimización de divide y vencerás (D&C) para hallar todos los $opt_i$ .

Podemos usar un Árbol de Fenwick (BIT) o cualquier otra estructura de datos adecuada para consultar el número de puntos en un rectángulo de forma eficiente.

Implementación

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

Complejidad espacial: $\mathcal{O}(N)$


#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
 
ll ans = 0, bit[100001];
int n, a[100001], b[100001];
vector<int> cand;
 
void update(int pos, ll val) {
	for (; pos <= n; pos += pos & (-pos)) bit[pos] += val;
}
 
ll query(int x, int y) {
	ll ans = 0;
	for (; y; y -= y & (-y)) ans += bit[y];
	for (x--; x; x -= x & (-x)) ans -= bit[x];
	return ans;
}
 
void divide_conquer(int l = 0, int r = cand.size() - 1, int l_opt = 0,
                    int r_opt = n - 1) {
	int mid = (l + r) / 2, opt = -1;
	ll best_delta = 1;
	FOR(i, max(l_opt, cand[mid]), r_opt + 1) {
		update(a[i], 1);
		int inv = 1 - query(a[i] + 1, a[cand[mid]] - 1) - query(a[i], a[cand[mid]]);
		if (inv <= best_delta) best_delta = inv, opt = i;
	}
	ans = min(ans, best_delta);
 
	if (mid != r) {
		FOR(i, cand[mid], cand[(mid + r + 1) / 2]) update(a[i], -1);
		FOR(i, max(opt, cand[(mid + r + 1) / 2]), r_opt + 1) update(a[i], -1);
		divide_conquer(mid + 1, r, opt, r_opt);
		FOR(i, cand[mid], cand[(mid + r + 1) / 2]) update(a[i], 1);
		FOR(i, max(opt, cand[(mid + r + 1) / 2]), r_opt + 1) update(a[i], 1);
	}
 
	if (mid != l) {
		FOR(i, cand[(mid + l - 1) / 2], min(l_opt, cand[mid])) update(a[i], 1);
		FOR(i, max(l_opt, cand[mid]), r_opt + 1) update(a[i], -1);
		divide_conquer(l, mid - 1, l_opt, opt);
		FOR(i, cand[(mid + l - 1) / 2], min(l_opt, cand[mid])) update(a[i], -1);
		FOR(i, max(l_opt, cand[mid]), r_opt + 1) update(a[i], 1);
	}
 
	FOR(i, max(l_opt, cand[mid]), r_opt + 1) update(a[i], -1);
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	bool sorted = true, distinct = true;
	FOR(i, 0, n) {
		cin >> a[i];
		b[i] = a[i];
		if (i) sorted &= (a[i] >= a[i - 1]), distinct &= (a[i] != a[i - 1]);
	}
	if (sorted) return cout << distinct << '\n', 0;
 
	sort(b, b + n);
	FOR(i, 0, n) {
		a[i] = lower_bound(b, b + n, a[i]) - b + 1;
		if (!i || a[i] > a[cand.back()]) cand.push_back(i);
	}
 
	divide_conquer();
	for (int i = n - 1; ~i; i--) {
		update(a[i], 1);
		ans += query(1, a[i] - 1);
	}
	cout << ans << '\n';
	return 0;
}