Dos veces en el intervalo
El pequeño Mirko es un hombre sencillo. Darko, el amigo de Mirko, le ha dado un arreglo de enteros y le hace
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 y
. La segunda línea de la entrada contiene
enteros menores que
, los elementos del arreglo. Cada una de las siguientes
líneas contiene dos enteros
y
, los extremos izquierdo y derecho de un intervalo en el arreglo.
Salida
La salida debe contener líneas, cada una conteniendo la respuesta a la pregunta respectiva.
Ejemplo #1 de Entrada
5 1
1 2 1 1 1
1 3Ejemplo #1 de Salida
1Ejemplo #2 de Entrada
5 2
1 1 1 1 1
2 4
2 3Ejemplo #2 de Salida
0
1Ejemplo #3 de Entrada
5 2
1 1 2 2 3
1 1
1 5Ejemplo #3 Salida
0
2
Comments
Alguien que explique una solución en
??
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.
Creo q es con persistent
Cómo se puede resolver esto en
o mejor?
Alquien podria darme alguna idea de como resolver este problema