Editorial

Let's declare three integer arrays $s[i](1\le i\le 3)$. The prefix sums for cows of breed $i$ will be stored in the array $s[i]$.

The answer to the query $(a,b)$ is computed as follows:

• The number of cows of breed $1$ is $s[1][b]-s[1][a-1]$;

• The number of cows of breed $2$ is $s[2][b]-s[2][a-1]$;

• The number of cows of breed $3$ is $s[3][b]-s[3][a-1]$;

Example

For the given example, the prefix sum arrays $s[i](1\le i\le 3)$ will be as follows:

Consider the query on the interval $(2,4)$:

• The number of cows of breed $1$ is $s[1][4]-s[1][1]=2-0=2$;

• The number of cows of breed $2$ is $s[2][4]-s[2][1]=1-1=0$;

• The number of cows of breed $3$ is $s[3][4]-s[3][1]=1-0=1$;

Algorithm realization

Declare arrays for storing prefix sums.

#define MAX 100001
int s[4][MAX];

Read the input data.

scanf("%d %d", &n, &q);

Compute the prefix sum arrays.

memset(s, 0, sizeof(s));
for (i = 1; i <= n; i++)
{
  scanf("%d", &x);
  for (j = 1; j <= 3; j++)
    s[j][i] = s[j][i - 1];
  s[x][i]++;
}

Process the $q$ queries sequentially.

for (i = 0; i < q; i++)
{
   scanf("%d %d", &a, &b);
   printf("%d %d %d\n", s[1][b] - s[1][a - 1], s[2][b] - s[2][a - 1], 
                        s[3][b] - s[3][a - 1]);
}