P6180 [USACO15DEC] Breed Counting S

Farmer John has $N$ cows, numbered from $1 \ldots N$ from left to right, standing in a line. All cows belong to one of three breeds, and each cow has a breed ID (only one of $1,2,3$). FJ has $Q$ queries, and each query asks for the number of cows of each breed within a certain interval.

The first line contains two integers $N, Q$ ($1 \leq N, Q \leq 10^5$). The next $N$ lines each contain one integer. The $i$-th integer represents the breed ID of the $i$-th cow. The next $Q$ lines each contain two integers $a, b$, meaning the range of the $i$-th query is $[a,b]$.

For each query, output three integers: the number of breed $1$ cows, the number of breed $2$ cows, and the number of breed $3$ cows in the specified interval.

Translated by ChatGPT 5