Números distintos

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 2.0s
C++11 2.0s
Java 8 8.0s
Python 8.0s
Memory limit: 320M
C++11 320M
Java 8 960M
Python 960M

Authors:
Problem type
Allowed languages
C++, Java, Python

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


  • 0
    Primervirgen  commented on Sept. 11, 2019, 12:57 a.m.

    No hay alguna otra vía de solución para este ejercicio aparte de Segment-tree? Quizás ABI????


    • 0
      aniervs  commented on Sept. 15, 2019, 12:59 a.m.

      Se puede resolver con el algoritmo de Mo.