Breed Counting.

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 128M

Author:

FrankHG

Problem type

Allowed languages

C, C++, Java, Pascal, Python, VB

Las $N$ ~N~ vacas del Granjero Juan, convenientemente numeradas $1...N$ ~1...N~, están paradas en una fila (ellas hacen eso tan frecuentemente que ahora le cuesta poco al Granjero Juan alinearlas). Cada vaca tiene un identificador de raza: 1 para Holsteins, 2 para Guernseys y 3 para Jerseys. Al Granjero Juan le gustaria su ayuda contando el número de vacas de cada raza que están en cierto intervalo del ordenamiento.

Entrada

La primera línea de la entrada contiene $N$ ~N~ y $Q$ ~Q~ $( 1 \leq N, Q \leq 100,000)$ ~( 1 \leq N, Q \leq 100,000)~.

Las siguientes $N$ ~N~ líneas contienen un entero que es 1, 2 ó 3, dando el identificador de raza de una sola vaca en el ordenamiento.

Las siguientes $Q$ ~Q~ líneas describen una pregunta en la forma de dos enteros $a,b$ ~a,b~ $(a \leq b)$ ~(a \leq b)~.

Salida

Para cada una de las $Q$ ~Q~ preguntas $(a, b)$ ~(a, b)~, imprima una línea conteniendo tres números: el número de vacas numeradas $a...b$ ~a...b~ que son Holsteins (raza 1), Guernseys (raza 2) y Jerseys (raza 3).

Ejemplo de Entrada

Ejemplo de Salida

3 2 1    
1 0 0    
2 0 1

Comments

-1

Rafael_Balseiro commented on Dec. 14, 2025, 9:28 p.m.

Alguien me puede dar una idea de como hacer este ejercicio? No se me ocurre nada

-3

eblabrada commented on Dec. 14, 2025, 10:18 p.m.

Mantén tres sumas de prefijos: una para Holsteins, una para Guernseys y otra para Jerseys. Esto permite calcular la cantidad de vacas de cada raza en un intervalo dado.

Específicamente, la respuesta en el intervalo $[l,r]$ ~[l,r]~ se puede calcular con $p[r] - p[l-1]$ ~p[r] - p[l-1]~, donde $p$ ~p~ es la suma de prefijos correspondiente.

0

Rafael_Balseiro commented on Dec. 15, 2025, 3:45 a.m.

No sabes cuanto te lo agradezco, me sirvió