1. Идея

Дан отсортированный по неубыванию массив стоимостей. Нужно посчитать, сколько элементов лежит в диапазоне [L, R].

Перебирать все элементы можно, но в задаче явно требуется использовать двоичный поиск. Значит, нужно найти:

• первую позицию, где элемент не меньше L;
• первую позицию, где элемент строго больше R.

Тогда все элементы между этими позициями как раз и будут принадлежать отрезку [L, R].

Ответ равен:

right - left

где:

• left — индекс первого элемента >= L;
• right — индекс первого элемента > R.

2. Наблюдения

Наблюдение 1

Массив уже отсортирован. Это позволяет искать границы диапазона двоичным поиском за O(log n).

Наблюдение 2

Если найти первый индекс left, где a[left] >= L, то:

• все элементы левее точно меньше L;
• начиная с left могут идти подходящие элементы.

Наблюдение 3

Если найти первый индекс right, где a[right] > R, то:

• все элементы левее right не больше R;
• начиная с right элементы уже не подходят.

Наблюдение 4

Подходящие элементы образуют непрерывный отрезок индексов: от left до right - 1.

Поэтому их количество равно right - left.

3. Алгоритм

Шаг 1

Считываем n, L, R и массив a.

Шаг 2

Находим left — первый индекс, где a[i] >= L.

Для этого используем двоичный поиск на полуинтервале [0, n):

• если a[m] >= L, то ответ может быть в левой половине, сдвигаем r = m;
• иначе a[m] < L, значит нужно искать правее, делаем l = m + 1.

Шаг 3

Находим right — первый индекс, где a[i] > R.

Снова двоичный поиск:

• если a[m] > R, идём влево: r = m;
• иначе a[m] <= R, идём вправо: l = m + 1.

Шаг 4

Выводим right - left.

4. Почему это работает

Докажем корректность.

Поиск left

После завершения первого двоичного поиска индекс left — это первая позиция, на которой стоит число не меньше L.

Это означает:

• для всех индексов i < left выполнено a[i] < L;
• для всех индексов i >= left, начиная с первой подходящей позиции, элементы могут быть >= L.

Значит, все элементы, которые могут входить в ответ, начинаются не раньше left.

Поиск right

После завершения второго двоичного поиска индекс right — это первая позиция, на которой стоит число строго больше R.

Это означает:

• для всех i < right выполнено a[i] <= R;
• для всех i >= right элементы уже больше R и не подходят.

Значит, все подходящие элементы заканчиваются на позиции right - 1.

Совмещение двух границ

Тогда элемент массива подходит тогда и только тогда, когда одновременно выполняется:

• a[i] >= L;
• a[i] <= R.

Из свойств найденных границ это равносильно условию:

• left <= i < right.

Таких индексов ровно right - left, значит именно это число и является ответом.

5. Сложность

Каждый двоичный поиск работает за O(log n).

Итоговая сложность:

• время: O(log n)
• память: O(1) дополнительной памяти, не считая самого массива

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int lower_bound_custom(const vector<long long>& a, long long x) {
    int l = 0;
    int r = (int)a.size();
    while (l < r) {
        int m = l + (r - l) / 2;
        if (a[m] >= x) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    return l;
}

int upper_bound_custom(const vector<long long>& a, long long x) {
    int l = 0;
    int r = (int)a.size();
    while (l < r) {
        int m = l + (r - l) / 2;
        if (a[m] > x) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    return l;
}

int main() {
    int n;
    long long L, R;
    cin >> n >> L >> R;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int left = lower_bound_custom(a, L);
    int right = upper_bound_custom(a, R);

    cout << (right - left) << '\n';
    return 0;
}

7. Код на Python 3

n, L, R = map(int, input().split())
a = list(map(int, input().split()))

l = 0
r = n
while l < r:
    m = (l + r) // 2
    if a[m] >= L:
        r = m
    else:
        l = m + 1
left = l

l = 0
r = n
while l < r:
    m = (l + r) // 2
    if a[m] > R:
        r = m
    else:
        l = m + 1
right = l

print(right - left)