Inversiones en Rango


Submit solution


Points: 100 (partial)
Time limit: 3.0s
Memory limit: 512M

Authors:
Problem type
Allowed languages
C++

Dada una permutación p de n elementos. Procese q consultas de la forma:

  • Dados a, b, c y d (1 \leq a \leq b < c \leq d \leq n), diga la cantidad de pares (x, y) tal que a \leq x \leq b, c \leq y \leq d y p_x > p_y.

Entrada:

La primera línea contendrá un entero n, (2 \le n \le 6\,000), la cantidad de elementos de la permutación p.

La segunda línea contendrá n enteros p_1, p_2, ... p_n, los elementos de la permutación p.

La tercera línea contendrá un entero q, (1 \le q \le 500\,000), la cantidad de consultas.

Las siguientes q líneas contendrán cuatro enteros a, b, c y d (1 \leq a \leq b < c \leq d \leq n), la descripción de cada consulta.

Salida:

Imprima q líneas con un entero cada una, el resultado de cada consulta.

Subtareas:

  • Subtarea 1: Para todas las consultas se cumple que a = b y c = d, además n, q \leq 300 (8 puntos)
  • Subtarea 2: p = n, n-1, n-2, n-3, \cdots, 2, 1, es decir, p es una permutación descendente, además n \leq 3000 y q \leq 6\,000 (11 puntos)
  • Subtarea 3: n, q \leq 300 (10 puntos)
  • Subtarea 4: q \leq 6\,000 (21 puntos)
  • Subtarea 5: n \leq 3000 (36 puntos)
  • Subtarea 6: Sin restricciones adicionales (14 puntos)

Ejemplo de entrada:

6
1 6 2 5 3 4
4
1 2 4 6
2 4 6 6
1 4 5 6
1 1 2 6

Ejemplo de salida:

3
2
4
0

Comments

There are no comments at the moment.