1. Идея

Нужно много раз отвечать на запрос:

• даны числа x и y,
• надо узнать, сколько элементов массива лежат в диапазоне [x, y].

Если для каждого запроса просто перебирать весь массив, получится слишком медленно: O(n * q), что при n, q до 2 * 10^5 не подходит.

Поэтому основная идея такая:

1. один раз отсортировать все значения заказов;
2. для каждого запроса находить границы подходящих элементов двоичным поиском.

После сортировки все элементы, попадающие в диапазон [x, y], будут идти подряд. Значит, достаточно найти:

• первую позицию элемента, который не меньше x,
• первую позицию элемента, который больше y.

Разность этих позиций и будет количеством элементов в диапазоне.

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

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

Например, если отсортированный массив такой:

[-2, -2, 0, 3, 3]

Для запроса [-1, 2] подходят только элементы 0.
Они занимают подряд идущие позиции.

Для запроса [3, 3] подходят два элемента 3, они тоже стоят подряд.

Наблюдение 2. Нужны две стандартные границы

В отсортированном массиве удобно искать:

• lower_bound(x) — индекс первого элемента >= x;
• upper_bound(y) — индекс первого элемента > y.

Тогда все элементы с индексами от lower_bound(x) до upper_bound(y) - 1 включительно принадлежат диапазону [x, y].

Количество таких элементов:

upper_bound(y) - lower_bound(x)

Наблюдение 3. Повторы обрабатываются автоматически

Если в массиве есть одинаковые значения, ничего дополнительно делать не нужно.

Например, массив:

[-2, -2, 0, 3, 3]

Запрос [-2, -2]:

• lower_bound(-2) укажет на первый -2,
• upper_bound(-2) укажет сразу за последний -2.

Разность даст 2, что и нужно.

3. Алгоритм

1. Считать n.
2. Считать массив a из n чисел.
3. Отсортировать массив.
4. Считать число запросов q.
5. Для каждого запроса:
   • считать x и y,
   • найти left — позицию первого элемента >= x,
   • найти right — позицию первого элемента > y,
   • вывести right - left.

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

Пусть массив отсортирован.

Рассмотрим запрос [x, y].

• Все элементы, которые меньше x, нам не подходят.
• Все элементы, которые больше y, тоже не подходят.
• Значит, подходят только элементы со значениями от x до y включительно.

Так как массив отсортирован, то:

• сначала идут все элементы < x,
• потом идут все элементы из диапазона [x, y],
• потом идут все элементы > y.

Позиция left = lower_bound(x) — это первый индекс, где элемент уже не меньше x.
То есть слева от left все элементы точно меньше x.

Позиция right = upper_bound(y) — это первый индекс, где элемент уже больше y.
То есть начиная с right все элементы точно больше y.

Следовательно, все подходящие элементы находятся ровно на позициях от left до right - 1. Их количество равно right - left.

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

5. Сложность

• Сортировка массива: O(n log n)
• Каждый запрос: O(log n)
• Все запросы: O(q log n)

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

O(n log n + q log n)

Память:

• O(n) на хранение массива.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

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

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

    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        long long x, y;
        cin >> x >> y;

        auto left = lower_bound(a.begin(), a.end(), x);
        auto right = upper_bound(a.begin(), a.end(), y);

        cout << (right - left) << "\n";
    }

    return 0;
}

7. Код на Python 3

from bisect import bisect_left, bisect_right

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

q = int(input())
for _ in range(q):
    x, y = map(int, input().split())
    left = bisect_left(a, x)
    right = bisect_right(a, y)
    print(right - left)