Conteggio delle Razze (Editoriale)

Dichiariamo tre array di interi s[i]~(1 \le i \le 3). Le somme prefisse per le mucche di razza $i$ saranno contenute nell'array $s[i]$.

La risposta alla query $(a,b)$ viene calcolata come segue:

• Il numero di mucche di razza $1$ è uguale a s[1][b] - s[1][a - 1];

• Il numero di mucche di razza $2$ è uguale a s[2][b] - s[2][a - 1];

• Il numero di mucche di razza $3$ è uguale a s[3][b] - s[3][a - 1];

Esempio

Per l'esempio riportato, gli array delle somme prefisse s[i]~(1 \le i \le 3) saranno i seguenti:

Consideriamo una query sull'intervallo $(2,4)$:

• Il numero di mucche di razza $1$ è uguale a s[1][4] - s[1][1] = 2 - 0 = 2;

• Il numero di mucche di razza $2$ è uguale a s[2][4] - s[2][1] = 1 - 1 = 0;

• Il numero di mucche di razza $3$ è uguale a s[3][4] - s[3][1] = 1 - 0 = 1;

Implementazione dell'algoritmo

Dichiariamo un array per memorizzare le somme parziali.

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

Leggiamo i dati di input.

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

Calcoliamo gli array delle somme parziali.

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]++;
}

Elaboriamo in sequenza $q$ query.

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]);
}

Implementazione in Python

import sys

Leggiamo i dati di input.

n, q = map(int, input().split())

Dichiariamo una lista per memorizzare le somme parziali.

s = [[0] * (n + 1) for _ in range(4)]

Calcoliamo gli array delle somme parziali.

for i in range(1, n + 1):
  x = int(input())
  for j in range(1, 4):
    s[j][i] = s[j][i - 1]
  s[x][i] += 1

Elaboriamo in sequenza $q$ query.

for _ in range(q):
  a, b = map(int, input().split())
  print(s[1][b] - s[1][a - 1], s[2][b] - s[2][a - 1], 
        s[3][b] - s[3][a - 1])