Cinsin hesablanması (Həll təhlili)

Üç tam ədədli massiv elan edək: s[i]~(1 \le i \le 3). $i$ cinsli inəklər üçün prefiks cəmləri $s[i]$ massivində saxlanılacaq.

$(a,b)$ sorğusuna cavab aşağıdakı qaydada hesablanır:

• $1$-ci cins inəklərin sayı s[1][b] - s[1][a - 1]-ə bərabərdir;

• $2$-ci cins inəklərin sayı s[2][b] - s[2][a - 1]-ə bərabərdir;

• $3$-cü cins inəklərin sayı s[3][b] - s[3][a - 1]-ə bərabərdir;

Nümunə

Verilmiş nümunə üçün s[i]~(1 \le i \le 3) prefiks cəmləri massivləri aşağıdakı kimi olacaq:

$(2,4)$ intervalı üzrə sorğuya baxaq:

• $1$-ci cins inəklərin sayı s[1][4] - s[1][1] = 2 - 0 = 2-yə bərabərdir;

• $2$-ci cins inəklərin sayı s[2][4] - s[2][1] = 1 - 1 = 0-a bərabərdir;

• $3$-cü cins inəklərin sayı s[3][4] - s[3][1] = 1 - 0 = 1-ə bərabərdir;

Alqoritmin realizasiyası

Qismi cəmləri saxlamaq üçün massiv elan edək.

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

Giriş məlumatlarını oxuyuruq.

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

Qismi cəmlər massivlərini hesablayırı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$ sorğunu ardıcıl olaraq emal edirik.

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 realizasiyası

import sys

Giriş məlumatlarını oxuyuruq.

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

Qismi cəmləri saxlamaq üçün siyahı elan edək.

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

Qismi cəmlər massivlərini hesablayırıq.

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$ sorğunu ardıcıl olaraq emal edirik.

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