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

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

На прошлой тренировке мы искали ответ по прямой формуле и префиксным суммам на отсортированном массиве. Сегодня — следующий шаг: что делать, когда массив исходно не отсортирован, но из него можно построить вспомогательный массив, который отсортирован всегда — и по нему уже искать ответ бинарным поиском. Вторая задача сессии — про решето Эратосфена, но не в чистом виде «найди все простые до N», а как быстрый способ отвечать на десятки тысяч вопросов о числах до $10^{12}$. Это предпоследняя тренировка «разогрева»: после сегодняшней сессии останется всего одна, которая станет мостиком к более длинным сессиям «плато».

---

Теория

Бинарный поиск по вспомогательному массиву, а не по исходному. Если сам массив не отсортирован (и сортировать нельзя — порядок важен для ответа), из него можно построить другой массив, который отсортирован всегда, и искать уже по нему.

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

• вопрос звучит как «до какого места можно дойти» или «докуда достижимо»;
• исходные данные идут в произвольном порядке, но их накопительная характеристика (например, максимум слева направо) растёт монотонно.

Как решать:

1. Строим вспомогательный массив за один проход — например, префиксный максимум: на позиции $i$ храним наибольшее значение среди первых $i$ элементов.
2. Такой массив всегда неубывающий (максимум не может уменьшиться при добавлении элементов).
3. Применяем бинарный поиск уже к вспомогательному массиву, а не к исходному.

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

Решето Эратосфена как инструмент быстрых проверок, а не только «найти все простые». Решето можно строить не только для задачи «выведи все простые до N» — им удобно быстро отвечать на много вопросов о простоте чисел.

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

• числа в условии большие (например, до $10^{12}$);
• но интересующее свойство (например, простота корня числа) сводится к диапазону, который решетом реально покрыть (до $10^6$, если исходные числа — квадраты).

Как решать:

1. Строим решето один раз — но только до той границы, которая реально нужна (например, до $\sqrt{10^{12}} = 10^6$), а не до границы исходных чисел.
2. Каждая проверка простоты дальше — это просто чтение готового значения за $O(1)$.

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

---

Задача 1 — CF ~1200 — «Scuza»

Что дано

Лестница из $n$ ступеней. Ступень $i$ выше предыдущей на $a_i$ метров (первая ступень выше земли на $a_1$ метров, земля — на высоте 0).

Дано $q$ независимых вопросов. В вопросе $i$ задана длина ног $k_i$. Взойти на ступень $j$ можно только если длина ног не меньше прироста высоты именно этой ступени: $k_i \ge a_j$. Подниматься можно только последовательно, начиная с первой ступени — как только встречается ступень с приростом больше $k_i$, подъём останавливается. Нужно для каждого вопроса вывести максимальную высоту, которой можно достичь.

Ограничения: количество тестов $t \le 100$. В каждом тесте $1 \le n, q \le 2 \cdot 10^5$ (суммарно по всем тестам $n$ и $q$ не превышают $2 \cdot 10^5$ каждое). $1 \le a_i \le 10^9$, $0 \le k_i \le 10^9$. Ответ может не поместиться в 32-битный тип — нужен 64-битный (long long).

Формат ввода: первая строка — $t$. Для каждого теста: строка с $n$ и $q$; строка с $n$ значениями $a_i$; строка с $q$ значениями $k_i$.

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

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

Первый тест: $a = [1, 2, 1, 5]$, вопросы $k = [1, 2, 4, 9, 10]$.

Обратите внимание: массив приростов не отсортирован ($1, 2, 1, 5$ — не по возрастанию). Наивная мысль «раз ноги длиной $k$, поднимемся, пока прирост ступени $\le k$» работает, но подниматься нужно последовательно с первой ступени, а не выбирая ступени в удобном порядке.

• $k=1$: ступень 1 — прирост 1, ОК (высота 1). Ступень 2 — прирост 2 > 1, стоп. Ответ — 1.
• $k=2$ или $k=4$: ступени 1, 2, 3 — приросты $1, 2, 1$, все $\le 4$, ОК. Ступень 4 — прирост 5 > 4, стоп. Высота $1+2+1=$ 4.
• $k=9$ или $k=10$: все приросты $\le 9$. Высота $1+2+1+5=$ 9.

Появляется наблюдение: чтобы дойти до ступени $j$, нужно, чтобы ВСЕ приросты $a_1, \ldots, a_j$ были $\le k$, а не только $a_j$. Иначе подъём остановился бы раньше. То есть условие достижимости ступени $j$ — это max(a_1, ..., a_j) <= k.

Идея решения

Ключевое наблюдение: обозначим $M_j = \max(a_1, \ldots, a_j)$ — префиксный максимум. Эта последовательность всегда неубывающая, независимо от того, как выглядит исходный массив $a$. Ступень $j$ достижима при длине ног $k$ тогда и только тогда, когда $M_j \le k$.

Раз $M$ неубывает, множество достижимых индексов — это всегда префикс $\{1, \ldots, m\}$ для наибольшего $m$, при котором $M_m \le k$ (или $m=0$, если даже $M_1 > k$). А раз $M$ отсортирован (неубывает) — искать такое $m$ можно бинарным поиском за $O(\log n)$ на запрос, вместо перебора ступеней для каждого вопроса.

Ответ на вопрос — это префиксная сумма $S_m = a_1 + \cdots + a_m$ (или 0, если $m=0$).

Почему это корректно (доказательство): если ступень $j$ достижима, то по определению подъёма все ступени $1, \ldots, j$ пройдены без остановки, то есть $a_1, \ldots, a_j \le k$ — а значит и их максимум $\le k$. Обратное тоже верно: если $M_j \le k$, то каждый отдельный $a_i \le M_j \le k$ для $i \le j$, значит ни на одной из ступеней $1, \ldots, j$ подъём не прервётся. Индукция по $j$ замыкает доказательство: достижимость ступеней — это ровно префикс, определяемый условием на префиксный максимум.

Строим два вспомогательных массива за один проход — $M$ (префиксный максимум) и $S$ (префиксная сумма) — а дальше каждый запрос обрабатывается независимым бинарным поиском по $M$.

Псевдокод

для каждого теста:
    прочитать n, q, массив a[1..n], массив k[1..q]

    M[0] = -бесконечность (или 0, т.к. a_i >= 1)
    S[0] = 0
    для i от 1 до n:
        M[i] = max(M[i-1], a[i])
        S[i] = S[i-1] + a[i]

    для каждого запроса k_i:
        m = наибольший индекс j такой, что M[j] <= k_i
             (бинарный поиск upper_bound по неубывающему массиву M)
        если такого j нет:
            ответ = 0
        иначе:
            ответ = S[m]
        вывести ответ

Код решения

Комментарии по реализации. Оба варианта строят два вспомогательных массива за один линейный проход, а дальше каждый запрос обрабатывается независимым бинарным поиском: Python — bisect_right из стандартной библиотеки на списке prefix_max; C++ — std::upper_bound на vector<long long>. В обоих случаях bisect_right/upper_bound возвращают индекс первого элемента, который строго больше искомого значения — то есть количество элементов $\le k$, что совпадает с наибольшим достижимым $m$ напрямую, без ручной коррекции границ.

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

Тест 1: $a=[1,2,1,5]$ → $M=[1,2,2,5]$, $S=[1,3,4,9]$.

Совпадает: 1 4 4 9 9.

Тест 2: $a=[1,1]$ → $M=[1,1]$, $S=[1,2]$.

Совпадает: 0 2.

Тест 3: $a=[10^9, 10^9, 10^9]$ → $M=[10^9, 10^9, 10^9]$, $S=[10^9, 2\cdot10^9, 3\cdot10^9]$.

При $k=10^9$: $m=3$, ответ $S[3] = 3 \cdot 10^9 = 3000000000$. Совпадает с ожиданием.

Все три теста сошлись.

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

• $k = 0$. Поскольку по ограничениям $a_i \ge 1$, ни одна ступень не достижима — ответ всегда 0.
• Все приросты равны и равны $k$. Достижимы все ступени, ответ — сумма всего массива.
• Массив не отсортирован произвольно (как в примере): алгоритм не требует сортировки исходного $a$ — работает именно предвычисленный префиксный максимум.
• Большая сумма. При $n, a_i$ у верхней границы сумма высоты может достигать $2 \cdot 10^5 \cdot 10^9 = 2 \cdot 10^{14}$ — не помещается в 32-битный int, нужен long long/64-битный тип.

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

1. int вместо long long в C++. Суммы до $2 \cdot 10^{14}$ переполняют 32-битный int.
2. Попытка бинарного поиска прямо по исходному массиву $a$, который не отсортирован — работает только по префиксному максимуму $M$.
3. bisect_left/lower_bound вместо bisect_right/upper_bound. Первый вариант ищет первый элемент $\ge k$, что даёт не то количество при повторяющихся значениях в $M$ — нужен именно вариант «строго больше», считающий все элементы $\le k$.
4. Забыть обработать случай $m=0$ (ни одна ступень не достижима) — индексация S[m-1] при m=0 уйдёт в отрицательный индекс или undefined behaviour.
5. Считать вопросы не независимо — условие в статье явно требует отвечать на каждый вопрос отдельно, без накопления состояния между вопросами одного теста.

Сложность

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

---

Задача 2 — CF ~1300 — «T-primes»

Что дано

Простое число — число ровно с двумя различными положительными делителями. По аналогии определим T-простое число — число ровно с тремя различными положительными делителями.

Дан массив из $n$ чисел $x_1, \ldots, x_n$. Для каждого нужно определить, является ли оно T-простым.

Ограничения: $1 \le n \le 10^5$, $1 \le x_i \le 10^{12}$.

Формат ввода: первая строка — $n$; вторая строка — $n$ чисел $x_i$.

Формат вывода: $n$ строк: YES, если число T-простое, иначе NO.

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

Дан массив $[4, 5, 6]$.

• $4$: делители $\{1, 2, 4\}$ — ровно три. YES.
• $5$: делители $\{1, 5\}$ — два (обычное простое). NO.
• $6$: делители $\{1, 2, 3, 6\}$ — четыре. NO.

Замечаем: единственное число из трёх, у которого ровно три делителя, — это $4 = 2^2$, квадрат простого числа $2$.

Идея решения

Утверждение: число $t$ имеет ровно три различных делителя тогда и только тогда, когда $t = p^2$ для некоторого простого $p$.

Доказательство. В одну сторону: если $t = p^2$ ($p$ — простое), делители $t$ — это $1, p, p^2$, и все три различны (так как $p > 1$). Значит, ровно три делителя.

В обратную сторону: делители числа обычно разбиваются на пары $(d, t/d)$, кроме случая $d = \sqrt{t}$, когда пара «схлопывается» в один делитель. Нечётное количество делителей (три — нечётно) возможно только если $t$ — точный квадрат, $t = s^2$. Далее раскладываем $s$ на простые множители: если $s = p_1^{e_1} \cdots p_k^{e_k}$, то $t = s^2 = p_1^{2e_1} \cdots p_k^{2e_k}$, и число делителей $t$ равно $(2e_1+1)(2e_2+1)\cdots(2e_k+1)$ — произведение нечётных чисел. Это произведение равно ровно 3 только когда в произведении один множитель равен 3 (то есть один простой множитель с $e_i=1$), а остальных множителей нет вовсе (иначе произведение было бы больше 3, так как каждый множитель $\ge 1$, а $2e_i+1 \ge 3$ при $e_i \ge 1$). Значит, $s$ состоит из ровно одного простого множителя в первой степени, то есть $s = p$ — само простое число, и $t = p^2$.

Алгоритм: для каждого $x$ проверить, является ли оно точным квадратом $s^2$, и если да — проверить, простое ли $s$. Поскольку $x \le 10^{12}$, то $s \le 10^6$. Значит, достаточно построить решето Эратосфена для чисел до $10^6$ один раз — и дальше каждая проверка простоты $s$ занимает $O(1)$.

Псевдокод

MAXR = 10^6
построить решето Эратосфена is_prime[0..MAXR]
    (is_prime[0] = is_prime[1] = ложь, дальше стандартное решето)

прочитать n, массив x[1..n]
для каждого x_i:
    s = целочисленный корень из x_i (округление вниз, точное)
    если s * s == x_i и is_prime[s]:
        вывести YES
    иначе:
        вывести NO

Код решения

Комментарии по реализации. Python — math.isqrt считает целочисленный корень точно, без ошибок округления floating point, поэтому дополнительная коррекция не нужна. C++ — sqrtl на long double для чисел до $10^{12}$ обычно даёт верный результат, но у плавающей точки на границах точных квадратов возможна погрешность в 1, поэтому добавлена явная коррекция s в обе стороны перед сравнением s * s == x. Решето строится один раз до $10^6$, а не до $10^{12}$ — этого достаточно, так как $\sqrt{10^{12}} = 10^6$.

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

Совпадает.

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

• $x = 1$. $\sqrt{1}=1$, $1^2=1$ — точный квадрат, но $1$ не является простым числом (у него всего один делитель) — решето должно явно пометить is_prime[1] = 0. Ответ — NO.
• Точный квадрат составного числа. Например, $x=36=6^2$ — квадрат, но $6$ не простое → NO. Важно не путать «$x$ — точный квадрат» с «$x$ — T-простое»: нужны оба условия.
• Верхняя граница $x = 10^{12}$. Если $x=(10^6)^2=10^{12}$, то $s=10^6$ — граничное значение решета (включительно).
• Простое число рядом с границей решета, например $p=999983$ (простое, близкое к $10^6$): $x=p^2 \approx 9.9997 \cdot 10^{11} < 10^{12}$ — должно дать YES.

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

1. int вместо long long/64-бит для $x$. Значения до $10^{12}$ не помещаются в 32-битный int (максимум около $2.1 \cdot 10^9$).
2. Погрешность плавающей точки при извлечении корня. int(sqrt(x)) в языках без встроенного целочисленного корня может дать результат на 1 меньше или больше истинного из-за округления — обязательна коррекция (или использование точной целочисленной функции вроде math.isqrt).
3. Решето построено только до $\sqrt{10^6}=1000$, а не до $10^6$ — забыли, что решето нужно строить до границы корня, а не до границы исходных чисел.
4. is_prime[1] не помечен как «не простое» — по умолчанию некоторые массивы инициализируются единицами, и без явного is_prime[1]=0 число 1 ошибочно посчитается простым.
5. Путаница «точный квадрат» и «T-простое». Проверка только s*s==x без проверки простоты s даёт неверный ответ на составных квадратах вроде 36, 100, 144.

Сложность

Построение решета: $O(\text{MAXR} \log \log \text{MAXR})$, один раз. Обработка каждого числа: $O(1)$ после решета (плюс $O(\log x)$ на извлечение корня). Итого: $O(\text{MAXR} \log \log \text{MAXR} + n)$.

---

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

• Codeforces 1354B «Ternary String» (~CF 1200) — дана строка из символов 1, 2, 3; нужно найти длину кратчайшей непрерывной подстроки, содержащей все три символа хотя бы по разу (или вывести 0, если такой подстроки нет).
• Codeforces 459B «Pashmak and Flowers» (~CF 1300) — дан массив красоты $n$ цветков; нужно найти максимально возможную разницу красоты между двумя цветками и количество способов выбрать такую пару.
• Codeforces 492B «Vanya and Lanterns» (~CF 1200) — дан набор фонарей на улице длины $l$; нужно найти минимальный радиус освещения, при котором вся улица оказывается покрыта светом.
• Codeforces 123A «Prime Permutation» (~CF 1300) — по строке из строчных латинских букв определить, можно ли переставить символы так, чтобы для каждого простого числа $p \le |s|$ все позиции, кратные $p$, содержали одинаковый символ.

Прорешай их самостоятельно — если застрянешь, разбери с AI-партнёром на codepal.ru: он не даёт готовый ответ, а подводит к решению вопросами.

---

Что дальше

На следующей тренировке — последняя сессия «разогрева»: сортировка в связке с бинарным поиском и хэш-таблица, снова около CF ~1300, а после неё — переход на «плато» с более длинными и составными задачами.