Haircut

Pista 1

Supongamos que solo tuviéramos que calcular el número de inversiones cuando $j = N$ . ¿Cómo podemos hacerlo de forma eficiente?

Pista 2

Nótese que el número de inversiones nunca aumenta cuando $j$ disminuye. ¿Qué información adicional deberíamos reunir para poder obtener de forma eficiente la respuesta para $j = N - 1$ a partir de cuando $j = N$ ?

Solución

Análisis oficial (C++)

Explicación

Primero, necesitamos contar el número de inversiones. (Dato curioso: el número de inversiones también es una medida de cuán ordenado está un arreglo. Si un arreglo tiene 0 inversiones, está perfectamente ordenado de forma ascendente. A la inversa, si tiene el número máximo posible de inversiones, el arreglo está perfectamente ordenado de forma descendente.)

Una forma de contar inversiones es usar un Árbol de Fenwick (BIT). Pensemos en una inversión como un par de valores $a, b$ , con $a > b$ y $a$ apareciendo antes que $b$ en el arreglo. Entonces podemos calcular fácilmente, para cada valor del arreglo, el número de inversiones para las que es $b$ .

Para esto, usamos un BIT como tabla de frecuencias, llevando la cuenta del número de pelos de cada valor posible. Si nuestro BIT se llama tree, tree[i] nos dirá cuántas veces se ve $i$ en el arreglo de pelos. El truco es que, mientras completemos la tabla de frecuencias en el orden en que aparecen los elementos en el arreglo, también podemos usar la tabla de frecuencias para contar el número de inversiones, porque en cada momento la tabla de frecuencias solo contiene pelos a la izquierda del pelo que estamos considerando actualmente.

Eso nos lleva a este algoritmo:

Inicializar un BIT de modo que la frecuencia de cada valor sea 0.
Crear un arreglo inversions. inversions[b] guardará el número de pares de inversión con el segundo valor igual a $b$
Para cada pelo $h$ en el orden en que aparece en el arreglo (siendo $h$ la longitud del pelo):
1. Contar el número de pelos más altos que aparecen antes del pelo $h$ en el arreglo (que, en este momento, son simplemente las frecuencias de todos los valores mayores que $h$ ). Guardar esto en inversions[h].
2. Incrementar la frecuencia de $h$ en el BIT.

El número de inversiones sería entonces la suma de todos los valores que calculamos en el paso 3.1. Sin embargo, también hay que considerar los cortes de pelo. Si cortamos todos los pelos de longitud mayor que $n$ a $n$ , ¿qué significa eso? Significa que no puede haber inversiones con un $b \geq n$ , porque la definición de inversión es que $a > b$ , pero si $b \geq n$ entonces $a > n$ también debe ser cierto. Sin embargo, si esto es cierto, entonces tanto $a$ como $b$ se habrían cortado a longitud $n$ , y $(a, b)$ ya no sería una inversión.

Así, el número de inversiones si todos los pelos mayores que $n$ se cortan a longitud $n$ es simplemente la suma de los primeros $n - 1$ elementos del arreglo de inversiones (si $n$ es 0 entonces todos los pelos miden 0 unidades, así que hay 0 inversiones para $n = 0$ ). Esto es básicamente la suma de prefijos del arreglo inversions.

Implementación

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

JavaC++


 
import java.io.*;
import java.util.*;
 
public class Haircut {
	public static void main(String[] args) throws IOException {
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out =
		    new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
 
		int N = Integer.parseInt(f.readLine());
		StringTokenizer st = new StringTokenizer(f.readLine());
 
		int[] hairs = new int[N];
 
		for (int i = 0; i < N; i++) { hairs[i] = Integer.parseInt(st.nextToken()); }
 
		BIT tree = new BIT(N + 1);  // el pelo puede ser a lo sumo N
 
		long[] inversionsWithValue = new long[N + 1];
		// inversionsWithValue[i] == el número de inversiones usadas con todos
		// los pelos de longitud i
 
		for (int value : hairs) {
 
			// procesamos de izquierda a derecha, así que el árbol solo
			// tiene elementos a la izquierda de este. Por lo tanto,
			// el número de elementos mayores que este es el número de
			// inversiones.
			int numInversions = tree.getSum(value + 1, tree.size - 1);
			inversionsWithValue[value] += numInversions;
 
			tree.increase(value, 1);
		}
 
		long cumulativeInversions = 0;
		out.println(0);  // si todos los pelos se cortan a longitud 0, son todos iguales,
		                 // así que no hay inversiones posibles
		for (int j = 0; j < N - 1; j++) {
			cumulativeInversions += inversionsWithValue[j];
			out.println(cumulativeInversions);
		}
 
		out.close();
	}
 
	static class BIT {
		int size;
		int[] tree;
 
		public BIT(int size) {
			this.size = size;
			tree = new int[size + 1];
		}
 
		/**
		 * Cambia el valor en el índice i en change
		 * @param i
		 * @param change
		 */
		public void increase(int i, int change) {
			i++;  // Empezamos el BIT en el índice 0
			while (i < tree.length) {
				tree[i] += change;  // Actualizamos todos los padres
				i += i & -i;        // lowbit (~i + 1) es lo mismo que -i
			}
		}
 
		/**
		 * Asigna i a un valor
		 * @param i
		 * @param val
		 */
		public void set(int i, int val) { increase(i, val - get(i)); }
 
		/**
		 * Suma de todos los elementos hasta i inclusive
		 * @param i - índice
		 * @return
		 */
		public int getSum(int i) {
			i++;
			int sum = 0;
			while (i > 0) {  // Sumamos los valores de cada padre
				sum += tree[i];
				i -= i & -i;
			}
			return sum;
		}
 
		/**
		 * Obtiene la suma del rango [i, j]
		 * @param i - índice de inicio, inclusive
		 * @param j - índice de fin, inclusive
		 * @return suma del rango [i, j]
		 */
		public int getSum(int i, int j) {
			return getSum(j) - (i > 0 ? getSum(i - 1) : 0);
		}
 
		/**
		 * @param i - índice
		 * @return elemento en i
		 */
		public int get(int i) { return getSum(i, i); }
 
		/**
		 * Representación en string
		 * @return
		 */
		public String toString() {
			String out = "";
			for (int i = 0; i < size - 1; i++) { out += get(i) + " "; }
			out += get(size - 1);
			return out;
		}
	}
}

Esta implementación usa un Árbol de Segmentos en lugar de un BIT, pero la idea es la misma.


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
/** @return la suma entre a y b. */
int sum(vector<ll> &segtree, int a, int b) {
	int c = segtree.size() / 2;
	a += c;
	b += c;
	int s = 0;
	while (a <= b) {
		if (a % 2) s += segtree[a++];
		if (!(b % 2)) s += segtree[b--];
		a /= 2;
		b /= 2;
	}
	return s;
}
 
/** Incrementa el elemento en k en x en el Árbol de Segmentos. */
void add(vector<ll> &segtree, int k, ll x) {
	int c = segtree.size() / 2;
	k += c;
	segtree[k] += x;
	for (k /= 2; k >= 1; k /= 2) { segtree[k] = segtree[2 * k] + segtree[2 * k + 1]; }
}
 
int main() {
	ifstream fin("haircut.in");
 
	int n;
	fin >> n;
 
	int c = 0;
	while ((1 << c) <= n + 1) { c++; }
	c = 1 << c;
 
	vector<ll> segtree(2 * c);
	vector<ll> ans(n + 2);
	for (int i = 1; i <= n; i++) {
		int a;
		fin >> a;
		ans[a + 1] += sum(segtree, a + 1, n + 1);
		add(segtree, a, 1);
	}
 
	ofstream fout("haircut.out");
	ll total = 0;
	for (int i = 0; i < n; i++) {
		total += ans[i];
		fout << total << "\n";
	}
}