Saman tayalarının sayılması (Həll təhlili)

Saman tayalarının koordinatlarını sıraya düzək.

Qoy $f(x)$ — $[0;x]$ intervalında saman tayalarının sayı olsun. Beləliklə, $[a;b]$ intervalında saman tayalarının sayı f(b) - f(a - 1)-ə bərabər olacaq.

$f(x)$ dəyərini binar axtarış vasitəsilə tapırıq.

Alqoritmin reallaşdırılması

Giriş məlumatlarını oxuyuruq.

scanf("%d %d", &n, &q);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Saman tayalarının koordinatlarını sıraya düzək.

sort(v.begin(), v.end());

$q$ sorğuları emal edirik.

for (i = 0; i < q; i++)
{

$a$-dan $b$-yə qədər intervalında saman tayalarının sayını $res$ tapıb çıxarırıq.

  scanf("%d %d", &a, &b);
  res = upper_bound(v.begin(), v.end(), b) – 
        upper_bound(v.begin(), v.end(), a - 1);
  printf("%d\n", res);
}

Python reallaşdırılması

import bisect

Giriş məlumatlarını oxuyuruq.

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

Saman tayalarının koordinatlarını sıraya düzək.

v.sort()

$q$ sorğuları emal edirik.

for _ in range(q):

$a$-dan $b$-yə qədər intervalında saman tayalarının sayını $res$ tapıb çıxarırıq.

  a, b = map(int, input().split())
  res = bisect.bisect_right(v, b) - bisect.bisect_right(v, a - 1)
  print(res)