Підрахунок породи (Розбір)

Оголосимо три цілочисельних масиви s[i]~(1 \le i \le 3). Префіксні суми для корів породи $i$ будуть міститися в масиві $s[i]$.

Відповідь на запит $(a,b)$ обчислюється наступним чином:

• Кількість корів породи $1$ дорівнює s[1][b] - s[1][a - 1];

• Кількість корів породи $2$ дорівнює s[2][b] - s[2][a - 1];

• Кількість корів породи $3$ дорівнює s[3][b] - s[3][a - 1];

Приклад

Для наведеного прикладу масиви префіксних сум s[i]~(1 \le i \le 3) будуть наступними:

Розглянемо запит на інтервалі $(2,4)$:

• Кількість корів породи $1$ дорівнює s[1][4] - s[1][1] = 2 - 0 = 2;

• Кількість корів породи $2$ дорівнює s[2][4] - s[2][1] = 1 - 1 = 0;

• Кількість корів породи $3$ дорівнює s[3][4] - s[3][1] = 1 - 0 = 1;

Реалізація алгоритму

Оголосимо масив для зберігання часткових сум.

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

Читаємо вхідні дані.

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

Обчислюємо масиви часткових сум.

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

Послідовно обробляємо $q$ запитів.

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

Реалізація на Python

import sys

Читаємо вхідні дані.

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

Оголосимо список для зберігання часткових сум.

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

Обчислюємо масиви часткових сум.

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

Послідовно обробляємо $q$ запитів.

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