1. Идея

Нужно много раз отвечать на запрос: сколько элементов массива a не меньше числа t.

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

Главная идея — сначала отсортировать массив. Тогда для каждого порога t можно быстро найти первую позицию, где стоит число не меньше t. Все элементы справа от этой позиции тоже будут не меньше t, потому что массив отсортирован.

Остаётся только посчитать, сколько таких элементов: это n - pos, где pos — индекс первого элемента, не меньшего t.

Для поиска pos используем двоичный поиск.

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

1. После сортировки все элементы идут по возрастанию.

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

   -3 0 7 7 10

   и запрос t = 7, то первая подходящая позиция — индекс 2.
   Значит, подходят элементы с индексами 2, 3, 4, всего 5 - 2 = 3.

2. Если в массиве нет элементов, которые не меньше t, то ответ равен 0.

   В этом случае удобно считать, что позиция pos = n, и тогда n - pos = 0.

3. Если все элементы массива не меньше t, то первая подходящая позиция — 0, и ответ будет n.

4. Нам нужен именно первый индекс, где a[mid] >= t.

   Это стандартный вариант двоичного поиска на левую границу.

3. Алгоритм

1. Считать n.
2. Считать массив a.
3. Отсортировать массив.
4. Считать q.
5. Для каждого запроса:
   • считать t;
   • выполнить двоичный поиск по массиву, чтобы найти минимальный индекс pos, для которого a[pos] >= t;
   • если такого индекса нет, оставить pos = n;
   • вывести n - pos.

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

После сортировки массив обладает свойством:

• если некоторый элемент a[i] не меньше t, то все элементы правее, то есть a[i+1], a[i+2], ..., тоже не меньше t;
• если a[i] < t, то все элементы левее могут быть только меньше или равны a[i], то есть тоже меньше t.

Значит, массив как бы делится на две части:

• слева — элементы < t;
• справа — элементы >= t.

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

Двоичный поиск как раз умеет находить такую границу за логарифмическое время:

• если a[mid] >= t, то нужная позиция находится в левой половине или равна mid, поэтому запоминаем mid и двигаем правую границу;
• если a[mid] < t, то нужная позиция точно правее, поэтому двигаем левую границу.

Когда поиск заканчивается, pos — это первый индекс, где стоит число не меньше t, либо n, если такого элемента нет.

Тогда количество элементов, не меньших t, равно числу элементов от pos до n - 1, то есть n - pos.

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 t;
        cin >> t;

        int left = 0, right = n - 1;
        int pos = n;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (a[mid] >= t) {
                pos = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        cout << (n - pos) << '\n';
    }

    return 0;
}

7. Код на Python 3

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

q = int(input())

for _ in range(q):
    t = int(input())
    left = 0
    right = n - 1
    pos = n

    while left <= right:
        mid = (left + right) // 2
        if a[mid] >= t:
            pos = mid
            right = mid - 1
        else:
            left = mid + 1

    print(n - pos)