Codeforces 276C

http://codeforces.com/problemset/problem/276/C

La solución para este problema es incluir los números mas grandes en el arreglo en las posiciones donde sean mas consultados, para que contribuyan la mayor cantidad al resultado total. Para esto hay que calcular cuales son las posiciones que mas aparecen en las consultas. Esto se puede lograr usando un BIT e introducir cada intervalo de consulta como update(l, 1) y update(r+1, -1). Luego podemos consultar en el BIT dada una posición i, cuantos intervalos contienen esa posición  Ordenamos las posiciones descendentemente por la cantidad de intervalos que la contienen, y los números del arreglo en orden descendiente. Finalmente, cada numero en el arreglo original contribuye a la suma con T[i], donde T[i] es el valor de la cantidad de intervalos que contienen la posición i.

Existe otra forma de calcular la cantidad de intervalos que contienen una posición dada, que no requiere de ninguna estructura especial. Esto lo podemos calcular con un arreglo A[i]. Dado un intervalo [l, r], incrementamos A[l] y decrementamos A[r+1].

Después de procesar todos los intervalos, calculamos A[i] = A[1] + A[2] + … + A[i]. Dada una posición i, hay 3 casos:

  1. [l, r] termina antes que i. En este caso, se cancela el incremento en l con el decremento en r, y no se afecta el valor de A[i].
  2. [l, r] comienza después de i. En este caso, el incremento es después de la posición i, por tanto no se afecta su valor.
  3. [l, r] contiene a la posición i. En este caso, solo contamos el valor del incremento en l, ya que r esta después de i.

Esta técnica es mas sencilla y puede ser usada para muchos otros tipos de problemas en los que se requiera tratar con intervalos.

Mi solución en Codeforces http://codeforces.com/contest/276/submission/3203916

Anuncios

Un comentario en “Codeforces 276C

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