Підрахунок стогів сіна (Розбір)

Відсортуємо координати стогів сіна.

Нехай $f(x)$ — кількість стогів сіна в інтервалі $[0;x]$. Тоді кількість стогів сіна в інтервалі $[a;b]$ буде дорівнювати f(b) - f(a - 1).

Значення $f(x)$ знаходимо за допомогою бінарного пошуку.

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

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

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

Сортуємо координати стогів сіна.

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

Обробляємо $q$ запитів.

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

Знаходимо та виводимо кількість стогів сіна $res$ в інтервалі від $a$ до $b$ включно.

  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 реалізація

import bisect

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

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

Сортуємо координати стогів сіна.

v.sort()

Обробляємо $q$ запитів.

for _ in range(q):

Знаходимо та виводимо кількість стогів сіна $res$ в інтервалі від $a$ до $b$ включно.

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