Números distintos

Submit solution
Points: 100 (partial)
Time limit: 2.0s
Java 8 8.0s
Python 8.0s
Memory limit: 320M
Java 8 960M
Python 960M
Authors:
Forte11, ralcolea, rramirez, jabetancourt
Problem type
Allowed languages
Ada, BrainF***, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Prolog, Python, Swift, VB

Dada una secuencia de n números a1, a2, ..., an y varias consultas. Una consulta es un par (i, j) (1 ≤ i ≤ j ≤ n). Para cada consulta (i, j), debe devolver el número de elementos distintos en la subsecuencia ai, ai + 1, ..., aj.

Entrada

 Línea 1: n (1 ≤ n ≤ 10^5).
 Línea 2: n números a1, a2, ..., an (1 ≤ ai ≤ 10^6).
 Línea 3: q (1 ≤ q ≤ 10^5), el número de consultas.
 En las siguientes líneas q, cada línea contiene 2 números i, j que representan una consulta (1 ≤ i ≤ j ≤ n).

Salida

Para cada consulta (i, j), imprima el número de elementos distintos en la subsecuencia ai, ai + 1, ..., aj en una sola línea.

Ejemplo de entrada

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

Ejemplo de salida

4
1
4
2
4

Comments


  • -15
    Primervirgen  commented on Sept. 11, 2019, 4:57 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 10
      aniervs  commented on Sept. 15, 2019, 4:59 a.m.

      Se puede resolver con el algoritmo de Mo.