Pyramid Array

Explicación

El problema pide la cantidad mínima de intercambios adyacentes necesarios para transformar un arreglo en una pirámide (creciente y luego decreciente). Recordemos que la cantidad mínima de intercambios adyacentes para reordenar un arreglo es igual a la cantidad de inversiones entre los estados inicial y final.

Estrategia voraz inicial

Para minimizar las inversiones, debemos colocar los elementos de forma voraz. Consideremos procesar los elementos de mayor a menor.

El elemento más grande debe estar en el “pico” de la pirámide, que puede no estar en el centro del arreglo.
Para cada elemento siguiente, debemos colocarlo inmediatamente a la izquierda o inmediatamente a la derecha del “bloque central” formado por los elementos ya procesados.

Para minimizar el total de intercambios, simplemente calculamos el costo de ambas opciones:

Costo izquierdo: la cantidad de intercambios para mover $x$ a la izquierda del bloque. Esto es igual a la cantidad de elementos ya colocados (más grandes) que están actualmente a la izquierda de $x$ .
Costo derecho: la cantidad de intercambios para mover $x$ a la derecha del bloque. Esto es igual a la cantidad de elementos ya colocados (más grandes) que están actualmente a la derecha de $x$ .

Elegimos de forma voraz el mínimo de estos dos para cada elemento.

Por qué funciona lo voraz

Para garantizar el costo mínimo, debemos demostrar que nuestras elecciones son óptimas. Desglosemos el costo total en contribuciones individuales.

Para cualquier elemento $x$ , consideremos el conjunto de todos los elementos más grandes que él, denotado $S$ . En una estructura de pirámide válida, los valores crecen hasta un pico y luego decrecen. Esto implica que el conjunto de elementos más grandes $S$ debe formar un bloque contiguo en el centro del arreglo, y $x$ debe colocarse fuera de este bloque (ya sea inmediatamente a la izquierda o inmediatamente a la derecha).

Ambos casos tienen un costo asociado. Elegir el mínimo de estos da el costo mínimo para procesar el elemento actual $x$ . ¿Pero cómo garantiza eso el costo mínimo global?

De forma crucial, el costo de estas elecciones depende solo del arreglo de entrada inicial:

Costo izquierdo: la cantidad de intercambios necesarios para mover $x$ a la izquierda de $S$ es exactamente la cantidad de elementos de $S$ que están actualmente en índices menores que el índice de $x$ .
Costo derecho: la cantidad de intercambios necesarios para mover $x$ a la derecha de $S$ es exactamente la cantidad de elementos de $S$ que están actualmente en índices mayores que el índice de $x$ .

Como el costo de colocar $x$ depende solo de las posiciones originales de los elementos más grandes (y no de dónde terminan esos elementos más grandes), podemos tomar la decisión óptima para cada elemento de forma independiente. Minimizar el costo de cada elemento individualmente garantiza el mínimo global.

Algoritmo

Esto se reduce a contar dinámicamente la cantidad de inversiones. Modelamos el arreglo como una secuencia binaria donde un 1 representa un elemento ya procesado (más grande).

$L$ es la cantidad de elementos ya procesados (más grandes) ubicados a la izquierda del índice actual.
$R$ es la cantidad de elementos ya procesados (más grandes) ubicados a la derecha del índice actual.
Consulta: para hallar $L$ , necesitamos la suma de valores en el rango $[0, i-1]$ . Como procesamos $k$ elementos hasta ahora, podemos derivar $R$ como $k - L$ . Esto es una consulta de suma de rango.
Actualización: para marcar el índice $i$ como procesado, cambiamos el valor en $i$ de $0$ a $1$ . Esto es una actualización puntual.

Como necesitamos que ambas operaciones sean eficientes, usamos un Árbol de Fenwick (BIT) o una estructura de datos PURS similar.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{BIT}
template <class T> class BIT {
  private:
	int size;
	vector<T> bit;
	vector<T> arr;
 
  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {}
 
	/** Pone el valor en el índice ind a val. */
	void set(int ind, T val) { add(ind, val - arr[ind]); }
 
	/** Suma val al elemento en el índice ind. */
	void add(int ind, T val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}
 
	/** @return La suma de todos los valores en [0, ind]. */
	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}
};
// EndCodeSnip
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
 
	int n;
	cin >> n;
 
	// Guardar elementos como {valor, índice_original}
	vector<pair<int, int>> elements(n);
	for (int i = 0; i < n; i++) {
		cin >> elements[i].first;
		// Guardar índice 0-based para coincidir con la plantilla del BIT
		elements[i].second = i;
	}
 
	// Ordenar en orden descendente para procesar primero los elementos más grandes
	sort(elements.rbegin(), elements.rend());
 
	BIT<int> ft(n);
	long long total_swaps = 0;
 
	for (int i = 0; i < n; i++) {
		int current_pos = elements[i].second;
 
		// Calcular cuántos elementos más grandes ya están a la izquierda
		// pref_sum devuelve la suma en [0, current_pos - 1]
		int left_cost = ft.pref_sum(current_pos - 1);
 
		// Calcular cuántos elementos más grandes ya están a la derecha
		// 'i' es el total de elementos procesados hasta ahora (todos más grandes)
		int right_cost = i - left_cost;
 
		// Elegir de forma voraz el lado con menos intercambios (inversiones)
		total_swaps += min(left_cost, right_cost);
 
		// Marcar esta posición como ocupada (actualización puntual)
		ft.add(current_pos, 1);
	}
 
	cout << total_swaps << endl;
 
	return 0;
}