Тренировочная сессия 4: сортировка, бинарный поиск и суффиксные массивы СЕССИЯ

Что тренируем сегодня

В прошлой сессии мы разбирали первую жадность и сортировку по остаткам — сегодня остаёмся на сортировке, но добавляем к ней второй инструмент, без которого дальше никуда: бинарный поиск по уже отсортированным данным. Это не тот бинарный поиск «по ответу», с которым вы познакомитесь в сессии 5 — здесь всё проще и приземлённее: у нас есть отсортированный массив, и мы ищем в нём границу (первый элемент больше X, последний элемент не больше X и так далее) вместо линейного перебора.

Вторая идея сегодня — суффиксный массив предвычислений: вместо того чтобы на каждый запрос пересчитывать что-то с нуля за $O(n)$, мы один раз проходим по массиву справа налево и запоминаем ответ для каждой позиции. Это простой, но фундаментальный приём: если запросов много ($10^5$ и больше), one-pass-предвычисление превращает $O(n \cdot q)$ в $O(n + q)$ — при $n, q \sim 10^5$ разница на несколько порядков.

Обе задачи сегодня — на уровне CF ~1100, оперируют похожей структурой «дан массив + много запросов», но решаются принципиально разными техниками. Разбор именно этой пары должен закрепить, что первый вопрос при виде фразы «ответьте на $q$ запросов» — это не «как решить один запрос», а «как один проход предвычислений закрыть все запросы разом».

---

Теория

Бинарный поиск по отсортированному массиву. Массив отсортирован один раз, а дальше приходит много одинаковых по смыслу запросов — вместо перебора каждый раз ищем границу за $O(\log n)$.

Когда применять:

• массив не меняется между запросами;
• запросов много, и вопрос один и тот же для разных значений $X$ («сколько элементов $\le X$», «где граница между меньшими и большими»).

Как решать:

1. Сортируем массив один раз — $O(n \log n)$.
2. На каждый запрос ищем границу бинарным поиском — $O(\log n)$.
3. Используем готовые функции: upper_bound/bisect_right для «$\le X$», lower_bound/bisect_left для «$< X$» — вручную цикл писать не нужно.

Где ошибаются: путают, какая из двух функций нужна — нестрогое и строгое условие дают разный ответ при повторяющихся значениях в массиве, и разница видна только на тестах с дубликатами.

Суффиксное (или префиксное) предвычисление за один проход. Когда запрос звучит как «что происходит от позиции $l$ и до конца» — не считаем это заново на каждый запрос, а один раз проходим по массиву и запоминаем ответ для каждой позиции.

Когда применять:

• в условии — «суффикс»/«начиная с позиции» или «префикс»/«до позиции»;
• запросов много, и наивный пересчёт на каждый запрос дал бы $O(n)$ на запрос, итого $O(n \cdot q)$.

Как решать:

1. Замечаем: соседние суффиксы (или префиксы) отличаются ровно одним элементом.
2. Идём по массиву один раз в нужную сторону, накапливая ответ.
3. Дальше каждый запрос — просто чтение готового значения за $O(1)$.

Направление прохода должно совпадать с направлением накопления: слева направо для префиксов, справа налево для суффиксов.

Где ошибаются: перепутывают направление прохода и получают «зеркальный» результат.

---

Задача 1 — CF ~1100 — «Interesting drink»

Что дано

В городе есть $n$ магазинов, продающих один и тот же напиток. В $i$-м магазине бутылка стоит $x_i$ монет. Участник планирует покупать напиток $q$ дней подряд — в $i$-й день у него есть ровно $m_i$ монет. Для каждого дня нужно вывести, в скольких магазинах напиток по карману (цена в магазине $\le$ доступной суммы в этот день).

Ограничения:

• $1 \le n \le 100\,000$ — число магазинов;
• $1 \le x_i \le 100\,000$ — цена бутылки в каждом магазине;
• $1 \le q \le 100\,000$ — число дней;
• $1 \le m_i \le 10^9$ — сумма денег в $i$-й день.

Формат ввода:

n
x_1 x_2 ... x_n
q
m_1
m_2
...
m_q

Формат вывода: $q$ целых чисел — для каждого дня количество магазинов, где напиток по карману.

Разберём на примере

Возьмём пять магазинов с ценами $[3, 10, 8, 6, 11]$ и четыре запроса: $1, 10, 3, 11$.

Отсортируем цены по возрастанию: $[3, 6, 8, 10, 11]$.

Для первого запроса ($m=1$) — ни одна цена не $\le 1$, ответ $0$.

Для второго запроса ($m=10$) — в отсортированном массиве $[3, 6, 8, 10, 11]$ элементы $\le 10$ — это $3, 6, 8, 10$, их четыре. Заметьте: искать «сколько элементов $\le 10$» в отсортированном массиве — это ровно то же самое, что найти позицию, где кончается «блок маленьких» и начинается «блок больших», то есть найти границу за $O(\log n)$ вместо перебора всех $n$ цен.

Для третьего запроса ($m=3$) — элементы $\le 3$: только сама тройка, ответ $1$.

Для четвёртого ($m=11$) — все пять элементов $\le 11$, ответ $5$.

Итоговый ответ по всем дням: 0 4 1 5 — это в точности официальный пример условия задачи.

Идея решения

Алгоритм в одну фразу: отсортировать цены один раз, а для каждого запроса $m_i$ бинарным поиском найти количество цен $\le m_i$ (в терминах стандартных библиотек — upper_bound).

Почему это работает. Ключевое наблюдение: как только массив цен отсортирован, вопрос «сколько элементов $\le m$?» превращается в вопрос «где заканчивается префикс элементов $\le m$?» — а это ровно то, что ищет бинарный поиск по монотонному условию «$x_i \le m$» (условие «истинно» для всех элементов слева от границы и «ложно» для всех элементов справа, потому что массив отсортирован). Позиция этой границы и есть искомое количество — не нужно ничего складывать или явно проверять каждый элемент.

Сложность одного запроса — $O(\log n)$ вместо $O(n)$ при переборе. При $n, q \le 10^5$ разница принципиальна: $10^5 \cdot 10^5 = 10^{10}$ операций (перебор) против $10^5 \cdot \log_2(10^5) \approx 10^5 \cdot 17 \approx 1.7 \cdot 10^6$ операций (бинарный поиск) — на несколько порядков быстрее, укладывается в лимит времени с огромным запасом.

Важно не путать upper_bound и lower_bound. upper_bound(x, m) находит первую позицию, где элемент строго больше $m$ — и эта позиция как раз равна количеству элементов $\le m$ (все элементы до неё $\le m$ по определению отсортированности). lower_bound(x, m) даёт первую позицию, где элемент $\ge m$ — это количество элементов строго меньше $m$, что здесь неверно: условие задачи — «цена не выше суммы», то есть нестрогое $\le$.

Псевдокод

прочитать n
прочитать массив x[1..n]
отсортировать x по возрастанию

прочитать q
для каждого запроса m:
    ans = позиция первого элемента x, строго большего m
          (эквивалентно: количество элементов x, которые <= m)
    вывести ans

Код решения

Комментарии по реализации.

• Python — bisect_right из стандартной библиотеки bisect работает так же, как C++ upper_bound: возвращает позицию первого элемента, строго большего искомого значения.
• C++ — upper_bound требует отсортированного диапазона (уже обеспечено сортировкой выше) и работает за $O(\log n)$; результат — итератор, разница с begin() даёт нужный индекс-количество.
• Оба решения читают весь ввод целиком (sys.stdin.buffer.read() в Python, буферизованный cin с sync_with_stdio(false) в C++) — при $q$ до $10^5$ построчное чтение с input() в Python было бы заметно медленнее.

Проверка на примерах

Оба решения (Python и C++) прогнаны на этом входе и дают 0 4 1 5 — совпадает с ожиданием.

Крайние случаи

1. $m$ меньше самой дешёвой цены. Ответ должен быть $0$ — upper_bound/bisect_right корректно возвращает позицию $0$, если искомое значение меньше всех элементов массива.
2. $m$ больше или равно самой дорогой цене. Ответ должен быть $n$ (все магазины по карману) — граница поиска возвращает позицию за концом массива, что и есть $n$.
3. Повторяющиеся цены. Если несколько магазинов продают по одинаковой цене, все они корректно учитываются: upper_bound считает все вхождения значения, равного $m$, как «$\le m$», не пропуская дубликаты.
4. $n = 1$ или $q = 1$. Вырожденные размеры не требуют отдельной обработки — сортировка массива из одного элемента и один бинарный поиск работают без исключений.

Типичные ошибки

1. lower_bound вместо upper_bound. Даёт количество элементов строго меньше $m$ вместо «$\le m$» — на входах без повторов цены, равной $m$, ошибка незаметна, но при повторяющихся ценах ответ занижается.
2. Забыть отсортировать массив перед бинарным поиском. Без сортировки upper_bound/bisect_right дают неопределённый, чаще всего неверный результат — предпосылка бинарного поиска (монотонность/отсортированность) должна быть явно обеспечена в коде, а не предполагаться из условия.
3. Линейный перебор всех цен на каждый запрос. Технически корректно, но при $n=q=10^5$ даёт $10^{10}$ операций суммарно — превышение лимита времени. Отсортировать один раз и искать бинарно — обязательное требование по объёму данных, а не просто оптимизация.
4. Построчное чтение большого объёма ввода в Python через input(). При $10^5$ строк запросов это заметно медленнее, чем чтение всего потока целиком и разбор по пробельным символам.

Сложность

Время: $O((n + q) \log n)$ — сортировка $O(n \log n)$ плюс $q$ бинарных поисков по $O(\log n)$ каждый. Память: $O(n + q)$ на хранение массива цен и ответов.

---

Задача 2 — CF ~1100 — «Sereja and Suffixes»

Что дано

Дан массив из $n$ целых чисел $a_1, a_2, \ldots, a_n$. Дано $m$ запросов вида $l$ ($1 \le l \le n$): для каждого нужно вывести количество различных чисел среди $a_l, a_{l+1}, \ldots, a_n$ (то есть в суффиксе массива, начинающемся с позиции $l$).

Ограничения:

• $1 \le n, m \le 100\,000$;
• $1 \le a_i \le 100\,000$.

Формат ввода:

n m
a_1 a_2 ... a_n
l_1
l_2
...
l_m

Формат вывода: $m$ строк — для каждого запроса количество различных чисел в соответствующем суффиксе.

Разберём на примере

Массив: $a = [1, 2, 3, 4, 1, 2, 3, 4, 100000, 99999]$ (10 элементов), запросы — все позиции от 1 до 10.

Наивный подход — на каждый запрос $l$ пройтись по суффиксу $a_l \ldots a_n$ и посчитать различные числа через множество. Это работает, но за $O(n)$ на запрос, суммарно $O(n \cdot m)$ — при $n=m=10^5$ это $10^{10}$ операций, слишком медленно.

Ключевое наблюдение: суффикс, начинающийся с позиции $l$, отличается от суффикса, начинающегося с позиции $l+1$, ровно одним дополнительным элементом — $a_l$. Значит, если мы уже знаем количество различных чисел в суффиксе с позиции $l+1$, то ответ для позиции $l$ получается почти бесплатно: это то же самое количество, плюс единица, если $a_l$ ещё не встречался в суффиксе с позиции $l+1$ (то есть встречается здесь впервые, если идти справа налево).

Пройдём по примеру руками справа налево, храня множество уже увиденных чисел и счётчик различных:

Ответы для запросов $l=1,\ldots,10$: 6 6 6 6 6 5 4 3 2 1 — совпадает с официальным примером условия.

Идея решения

Алгоритм в одну фразу: пройти по массиву один раз справа налево, поддерживая множество/булев массив «встречалось ли значение», и на каждой позиции сохранить текущее количество различных чисел в суффиксе — это и есть ответ на запрос с этой позицией.

Почему это работает. Определим $d(i)$ — количество различных чисел в суффиксе, начинающемся с позиции $i$. По определению $d(n+1) = 0$ (пустой суффикс). Переход: $d(i) = d(i+1) + 1$, если $a_i$ не встречается среди $a_{i+1}, \ldots, a_n$ (то есть добавление $a_i$ увеличивает множество различных значений), и $d(i) = d(i+1)$, если $a_i$ уже встречался в этом суффиксе (тогда добавление $a_i$ не меняет множество различных значений — оно уже там). Проверка «встречался ли $a_i$ в суффиксе с $i+1$» делается быстро, если идти именно справа налево и поддерживать множество уже увиденных значений: к моменту обработки позиции $i$ множество как раз и содержит все значения из суффикса $i+1, \ldots, n$.

Это классический пример суффиксного предвычисления: раз мы всё равно должны просмотреть весь массив хотя бы один раз, чтобы ответить хоть на один запрос корректно, — выгоднее сделать это один раз для всех позиций сразу, а не по отдельности для каждого запроса. После предвычисления массива $d[1..n]$ каждый запрос отвечается за $O(1)$ простым обращением по индексу.

Псевдокод

прочитать n, m
прочитать массив a[1..n]

seen = пустое множество (или булев массив размера maxValue+1)
d[n+1] = 0
для i от n до 1 (включительно, по убыванию):
    если a[i] не в seen:
        добавить a[i] в seen
        d[i] = d[i+1] + 1
    иначе:
        d[i] = d[i+1]

для каждого запроса l:
    вывести d[l]

Код решения

Комментарии по реализации.

• Python — булев массив seen фиксированного размера $100001$ (по ограничению $a_i \le 10^5$) быстрее, чем set(), за счёт отсутствия хеширования; при желании set() тоже работает корректно, но чуть медленнее на больших $n$.
• C++ — vector<char> вместо vector<bool> для seen: vector<bool> в C++ — специализация с побитовой упаковкой, которая имеет более высокую константу на операциях чтения/записи, char быстрее и понятнее для простого флага.
• Массив $d$ имеет размер $n+2$, а не $n+1$, чтобы безопасно обращаться к $d[n+1] = 0$ (база рекурсии для последней позиции) без выхода за границы.

Проверка на примерах

Оба решения (Python и C++) прогнаны на этом входе и дают 6 6 6 6 6 5 4 3 2 1 — совпадает с ожиданием.

Крайние случаи

1. $l = n$ (запрос на последний элемент). Суффикс состоит из одного элемента — ответ всегда $1$. В таблице выше это позиция 10, значение $d[10] = 1$.
2. $l = 1$ (запрос на весь массив). Ответ равен общему количеству различных значений во всём массиве — в примере это $6$.
3. Все элементы массива одинаковые. Тогда $d[i] = 1$ для любой позиции $i$ (кроме случая, когда массив пуст, что по ограничениям $n \ge 1$ не происходит) — каждый суффикс содержит ровно одно различное значение.
4. Все элементы массива различны. Тогда $d[i] = n - i + 1$ — суффикс с позиции $i$ содержит ровно столько различных значений, сколько в нём элементов, потому что повторов нет вовсе.

Типичные ошибки

1. Проход слева направо вместо справа налево. Задача явно про суффиксы («от $l$ до конца массива») — переход $d(i) = d(i+1) \pm 1$ определён именно в направлении справа налево; если считать слева направо, придётся хранить совсем другую структуру (префиксы), не отвечающую на вопрос напрямую.
2. Забыть очистить/обнулить seen между тестами, если решение оборачивается в цикл по нескольким независимым тестовым случаям (в данной задаче тестовый случай один на весь ввод, но при переносе техники на многотестовые задачи — частая причина неверного ответа во втором и последующих тестах).
3. Наивный пересчёт множества различных значений на каждый запрос заново. Даёт $O(n)$ на запрос и $O(n \cdot m)$ суммарно — при $n = m = 10^5$ это $10^{10}$ операций, превышение лимита времени. Одно предвычисление за $O(n)$ обязательно.
4. Индексация массива $d$ без учёта, что запросы 1-индексированные. В условии $l$ отсчитывается от $1$ до $n$ — массив предвычислений должен быть согласован с этой же индексацией (в приведённом коде $a$ и $d$ оба явно 1-индексированы, a[i] соответствует $a_i$ из условия).

Сложность

Время: $O(n + m)$ — один проход по массиву для построения $d$, плюс $O(1)$ на каждый из $m$ запросов. Память: $O(n + \max(a_i))$ — массив $d$ плюс булев массив «встречалось».

---

Самостоятельная тренировка

Обязательный раздел — 4 задачи того же уровня, которые нужно прорешать самостоятельно, без разбора здесь:

• Codeforces 313B «Ilya and Queries» (~CF 1100) — дана строка из символов . и # и несколько запросов вида «сколько соседних одинаковых пар символов на отрезке [l, r)».
• Codeforces 1327A «Sum of Odd Integers» (~CF 1100) — для нескольких пар чисел $(n, k)$ определить, можно ли представить $n$ как сумму $k$ различных нечётных положительных чисел.
• Codeforces 166A «Rank List» (~CF 1100) — по списку результатов команд (число решённых задач и штрафное время) найти, сколько команд делят между собой заданное место в итоговой таблице.
• Codeforces 82A «Double Cola» (~CF 1100) — пятеро друзей стоят в очереди, и после каждого напитка человек «раздваивается» и оба его дубля встают в конец очереди; нужно определить, кто выпьет банку номер $n$.

Все четыре задачи используют идею предвычисления префиксов/сумм за один проход или прямого счёта позиции — тот же принцип, что в разобранной сегодня «Sereja and Suffixes», только в другой форме. Прорешай их самостоятельно — если застрянешь, разбери с AI-партнёром на codepal.ru: он не даёт готовый ответ, а подводит к решению вопросами.

---

Что дальше

На следующей тренировке остаёмся на уровне CF ~1100, но переходим от бинарного поиска по готовому массиву к принципиально другой идее — бинарному поиску по ответу, когда мы перебираем не элемент массива, а сам ответ, и проверяем его монотонным предикатом.