10559. Подсчет стогов сена

 

Фермер Джон разместил свои n стогов сена в различных точках одномерной дороги вдоль его фермы. Вам требуется ответить на q запросов, о том сколько стогов сена находится внутри указанного участка дороги.

 

Вход. Первая строка содержит n (1 ≤ n ≤ 105) и q (1 ≤ q ≤ 105). Следующая строка содержит n различных целых чисел, каждое в интервале 0 ... 109, указывающих местоположения стогов сена.

Каждая из последующих q строк содержит два целых числа a и b (0 ≤ a ≤ b ≤ 109), задающих запрос на количество стогов сена между a и b, включительно.

 

Выход. Выведите q строк. Для каждого запроса выведите количество стогов сена в соответствующем интервале.

 

Пример входа

Пример выхода

4 6

3 2 7 5

2 3

2 4

2 5

2 7

4 6

8 10

2

2

3

4

1

0

 

 

 

РЕШЕНИЕ

бинарный поисак

 

Анализ алгоритма

Отсортируем координаты стогов сена.

Пусть 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);

}