SPOJ 6256 INVCNT

www.spoj.com/problems/INVCNT/

Este problema puede ser resuelto con un árbol de Fenwick. Nos dan el arreglo A como entrada. A partir de este arreglo, podemos crear un BIT de tamaño 10^7. Para cada elemento en A, vamos a insertar 1 en la posición correspondiente en el BIT.

Por ejemplo, en el primer caso, los elementos son [3, 1, 2]. Insertamos 1 en la posición 3, 1 en la 1 y 1 en la 2.

Para responder cuantas inversiones se forman, podemos consultar cada vez que insertemos un numero, cuantos mayores que el se han insertado, esto es, consultar el intervalo [n+1, 10^7] en el BIT. En el ejemplo, después de insertar 1 en 3, tenemos 0 mayores que el, ya que no se ha insertado ninguno después de 3. Al insertar 1 en 1, tenemos 1 mayor que 1, ya que el 3 fue insertado antes. Y al insertar el 2, también tenemos 1 mayor que 2. Para dar la respuesta, sumamos la cantidad de inversiones para cada numero.

Anuncios

Comentar

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s