Dos veces en el intervalo


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

El pequeño Mirko es un hombre sencillo. Darko, el amigo de Mirko, le ha dado un arreglo de N enteros y le hace Q preguntas acerca del arreglo a las que Mirko debe responder.

Cada pregunta consiste de dos enteros, las posiciones de los extremos izquierdo y derecho de un intervalo en el arreglo. La respuesta es el número de valores diferentes que aparecen exactamente dos veces en el intervalo dado.

Entrada

La primera línea de la entrada contiene los enteros N y Q (1 \leq N,Q \leq 500 000). La segunda línea de la entrada contiene N enteros menores que 1 000 000000, los elementos del arreglo. Cada una de las siguientes Q líneas contiene dos enteros L y R (1 \leq L \leq R \leq N), los extremos izquierdo y derecho de un intervalo en el arreglo.

Salida

La salida debe contener Q líneas, cada una conteniendo la respuesta a la pregunta respectiva.

Ejemplo #1 de Entrada

5 1
1 2 1 1 1
1 3

Ejemplo #1 de Salida

1

Ejemplo #2 de Entrada

5 2
1 1 1 1 1
2 4
2 3

Ejemplo #2 de Salida

0
1

Ejemplo #3 de Entrada

5 2
1 1 2 2 3
1 1
1 5

Ejemplo #3 Salida

0 
2

Comments


  • 0
    aniervs  commented on Feb. 17, 2020, 5:47 p.m.

    Alguien que explique una solución en O(n\log n)??


    • 5
      dmesadiaz  commented on Feb. 19, 2020, 5:41 p.m.

      A ver hay una solución con persistent Pero tambien se puede resolver con un BIT ordenando las querys. En la posicion i vas a guardar las querys q comienzan en i. Luego vas recorriendo el arreglo de derecha a izquierda y vas guardando las posiciones en las q aparece cada nunero y con el BIT updates las posiciones en las q cada numero cuenta y volviendo 0 la suma acumulativa hasta las q no cuentan. Despues para cada query q comienza en i solo tienes q responder BIT en i.


    • 0
      oscarito  commented on Feb. 17, 2020, 6:48 p.m.

      Creo q es con persistent


  • 0
    aniervs  commented on Feb. 11, 2020, 6:25 p.m.

    Cómo se puede resolver esto en O((N+Q)\log N) o mejor?


  • 0
    dmesadiaz  commented on Feb. 5, 2020, 9:58 p.m.

    Alquien podria darme alguna idea de como resolver este problema