Тренировочная сессия 6: прямая формула и префиксные суммы на отсортированном массиве СЕССИЯ

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

Пятая сессия познакомила нас с бинарным поиском по ответу — первым инструментом, где вместо прямого вычисления мы угадываем ответ и проверяем догадку. Сегодня возвращаемся к более прямому стилю мышления, но поднимаем планку: обе задачи решаются без циклов по всем числам — либо замкнутой формулой, либо предвычислением, которое превращает каждый запрос в одну операцию O(1). Это верхняя часть коридора разогрева: рейтинг CF ~1200, чуть выше предыдущих сессий.

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

---

Теория

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

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

• нужно найти $k$-й элемент в очень длинной или бесконечной последовательности;
• свойство повторяется блоками: «каждое $n$-е число обладает свойством X».

Как решать:

1. Считаем, сколько полных «периодов» (блоков) укладывается до нужного элемента.
2. Одним арифметическим выражением находим ответ, не перебирая элементы поштучно.

Например: если свойством обладает каждое 3-е число, а нужен 10-й элемент по счёту среди таких чисел, ответ — это просто $10 \times 3$ с поправкой на начало отсчёта.

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

Префиксные суммы сразу по двум массивам — исходному и отсортированному. Это тот же приём предвычисления за один проход из сессии 4, только применённый дважды — к обычному массиву и к его отсортированной копии.

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

• запросы явно делятся на два типа: одни — про элементы «как они даны», другие — про элементы «как они были бы после сортировки».

Как решать:

1. Строим массив префиксных сумм для исходного порядка.
2. Отдельно строим такой же массив для отсортированной копии.
3. Любой запрос суммы на отрезке — одно вычитание prefix[r] - prefix[l-1], независимо от того, к какому из двух массивов он относится.

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

---

Задача 1 — CF ~1200 — «K-th Not Divisible by n»

Что дано

Даны два положительных целых числа $n$ и $k$. Нужно вывести $k$-е по счёту положительное целое число, которое не делится на $n$.

Например, при $n = 3$ и $k = 7$: числа, не делящиеся на 3, — это $1, 2, 4, 5, 7, 8, 10, 11, 13, \ldots$. Седьмое число в этом списке — $10$.

Формат ввода: первая строка содержит число $t$ ($1 \le t \le 1000$) — количество независимых тестовых случаев. Далее идут $t$ строк, в каждой — два целых числа $n$ и $k$ ($2 \le n \le 10^9$, $1 \le k \le 10^9$).

Формат вывода: для каждого теста — одно число, $k$-е положительное целое, не делящееся на $n$.

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

Возьмём $n = 3$, $k = 7$. Выпишем первые числа подряд и отметим, какие делятся на 3:

Число 10 — седьмое среди тех, что не делятся на 3. Совпадает с ответом из условия.

Заметим закономерность: числа идут блоками по $n$ — в каждом блоке из $n$ подряд идущих чисел ровно одно делится на $n$ (последнее в блоке), а остальные $n - 1$ — не делятся. Блок 1, 2, 3 даёт 2 «хороших» числа (1, 2), блок 4, 5, 6 — ещё 2 (4, 5), блок 7, 8, 9 — ещё 2 (7, 8). Перебирать эти блоки по одному, пока не наберём $k$ штук, — рабочая идея, но при $k$ и $n$ до $10^9$ таких блоков может быть слишком много для перебора за отведённое время. Нужна формула, которая сразу «перепрыгивает» к нужному числу.

Идея решения

Идея в одну фразу: число блоков, которые нужно полностью пройти, чтобы набрать $k$ «хороших» чисел, — это $\lfloor (k - 1) / (n - 1) \rfloor$; прибавляем это количество к $k$ и получаем ответ.

Почему так: если бы все числа от 1 до какого-то $X$ не делились на $n$, ответом было бы просто $X = k$. Но начиная с числа $n$ (и далее $2n$, $3n$, …) через каждые $n$ чисел «теряется» ровно одно — то, что делится на $n$. Значит, чтобы досчитать до $k$-го «не делящегося» числа, нужно сдвинуться вправо на столько единиц, сколько кратных $n$ чисел встретится по дороге.

Формально: пусть ответ равен $x$. Среди чисел от 1 до $x$ ровно $\lfloor x/n \rfloor$ делятся на $n$, значит, не делящихся — ровно $x - \lfloor x/n \rfloor$. Нужно, чтобы это было равно $k$:

$$x - \left\lfloor \frac{x}{n} \right\rfloor = k$$

Прямо решать это уравнение относительно $x$ неудобно из-за целой части, но можно рассуждать через блоки: в каждом полном блоке из $n$ чисел — ровно $n - 1$ «хороших». Значит, чтобы накопить $k$ хороших чисел, нужно $\lfloor (k - 1) / (n - 1) \rfloor$ полностью пройденных кратных $n$ (используем $k - 1$, а не $k$, чтобы обработать пограничный случай, когда $k$ ровно делится на $n - 1$ — тогда последнее нужное число само оказывается последним перед очередным кратным, а не после него). Это количество кратных, оставшихся позади, и нужно прибавить к $k$, чтобы получить итоговое число:

$$x = k + \left\lfloor \frac{k - 1}{n - 1} \right\rfloor$$

Проверим интуицию на примере: $n = 3$, $k = 7$ — среди первых $x$ чисел на каждые 2 «хороших» приходится 1 «плохое» (кратное 3). Нужно 7 хороших → они укладываются в $\lceil 7 \cdot 3 / 2 \rceil$-окрестности, а точная формула даёт $7 + \lfloor 6/2 \rfloor = 7 + 3 = 10$ — ровно то, что мы посчитали руками.

Важный частный случай — $n = 2$. Тогда $n - 1 = 1$, и формула превращается в $x = k + (k - 1) = 2k - 1$ — это просто $k$-е нечётное число, что логично: числа, не делящиеся на 2, — это все нечётные.

Псевдокод

прочитать t
повторить t раз:
    прочитать n, k
    need = (k - 1) целочисленно_разделить (n - 1)
    ответ = k + need
    вывести ответ

Код решения

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

Полный набор примеров условия — шесть тестов в одном запуске:

Все шесть совпадают с ожидаемым выводом.

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

1. $n = 2$ — минимально допустимое значение $n$. Формула превращается в $2k - 1$ (см. вывод выше) — это тестируется вторым и последним примерами условия ($n=2, k=10^9$ и $n=2, k=1$), и оба совпадают.
2. $k$ кратно $(n-1)$ без остатка — например, $n=7, k=96$: тогда $need = \lfloor 95/6 \rfloor = 15$, а не $16$, как для $k=97$. Именно поэтому в формуле используется $k - 1$, а не $k$ — без этого сдвига на единицу ответ был бы занижен ровно на пограничных значениях.
3. Максимальные значения обоих чисел — $n = k = 10^9$: ответ немного больше $10^9$ ($1000000001$ в примере условия), что уже не помещается в диапазон int в C++ с запасом на промежуточные операции — отсюда long long.
4. $k = 1$ — первое «не делящееся» число всегда равно 1 (единица не делится ни на какое $n \ge 2$), формула даёт $need = \lfloor 0/(n-1) \rfloor = 0$, ответ $1$ при любом $n$.

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

1. int вместо long long в C++. При $n = k = 10^9$ ответ превышает $10^9$, и хотя сам по себе не переполняет 32-битный int (максимум ~$2.1 \times 10^9$), уже следующий подобный тест с чуть большими промежуточными вычислениями легко выйдет за границу — надёжнее сразу считать в long long.
2. Забыть -1 в числителе формулы. Частая ошибка — писать need = k / (n - 1) без сдвига. Это даёт неверный ответ ровно на пограничных значениях, где $k$ кратно $(n-1)$ (см. «Крайние случаи», пункт 2).
3. Целочисленное деление в Python через / вместо //. / вернёт float, и код либо упадёт при попытке вывести дробное число как позицию, либо даст видимо похожий, но неточный по типу результат.
4. Попытка честно перебирать числа one-by-one до $k$-го «не делящегося». При $n = k = 10^9$ цикл потребует до $2 \times 10^9$ итераций на один тест — с учётом $t \le 1000$ тестов это точно не уложится в лимит времени. Только формула.

Сложность

Время: $O(1)$ на тест, $O(t)$ суммарно. Память: $O(1)$.

---

Задача 2 — CF ~1200 — «Kuriyama Mirai's Stones»

Что дано

Дан массив из $n$ камней ($1 \le n \le 10^5$), пронумерованных от 1 до $n$; стоимость $i$-го камня — $v_i$ ($1 \le v_i \le 10^9$). Обозначим через $u_i$ стоимость $i$-го по счёту камня, если отсортировать все стоимости по неубыванию (то есть $u$ — это отсортированная копия массива $v$).

Дальше поступает $m$ запросов ($1 \le m \le 10^5$), каждый одного из двух типов, заданных числами type, $l$, $r$ ($1 \le l \le r \le n$):

• Тип 1 — вывести сумму $v_l + v_{l+1} + \ldots + v_r$ (сумма в исходном порядке массива).
• Тип 2 — вывести сумму $u_l + u_{l+1} + \ldots + u_r$ (сумма в отсортированном порядке).

Ответы на запросы могут превышать диапазон 32-битного целого числа.

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

Возьмём второй пример из условия: $n = 4$, массив $v = [5, 5, 2, 3]$.

Отсортируем копию массива по неубыванию: $u = [2, 3, 5, 5]$.

Разберём несколько запросов:

Ключевое наблюдение: массив $v$ и массив $u$ — это два разных массива одной и той же мультимножины чисел, и запросы к ним независимы. Если для каждого запроса заново суммировать элементы диапазона в цикле, при $n, m \le 10^5$ в худшем случае получим до $10^{10}$ операций — слишком медленно. Нужен способ отвечать на запрос суммы диапазона за $O(1)$.

Идея решения

Идея в одну фразу: посчитать заранее два массива префиксных сумм — один по исходному массиву $v$, второй по его отсортированной копии $u$ — и отвечать на каждый запрос одним вычитанием.

Префиксная сумма массива $a$ — это массив $P$, где $P_0 = 0$ и $P_i = P_{i-1} + a_i$ (сумма первых $i$ элементов). Тогда сумма элементов на отрезке $[l, r]$ равна $P_r - P_{l-1}$ — стандартный факт: $P_r$ включает всё от 1 до $r$, $P_{l-1}$ включает всё от 1 до $l-1$, разность оставляет ровно отрезок $[l, r]$.

Ничего не мешает применить этот же приём дважды к разным массивам: раз запросы типа 1 всегда про $v$, а запросы типа 2 всегда про $u$ (отсортированную копию), можно один раз построить $P^{v}$ и $P^{u}$, а дальше каждый запрос — это выбор нужного префиксного массива по типу и одно вычитание. Порядок элементов в $v$ и в $u$ разный, но каждый массив по отдельности статичен (не меняется между запросами) — значит, префиксные суммы считаются один раз и переиспользуются для всех $m$ запросов.

Псевдокод

прочитать n
прочитать массив v из n чисел

// префиксные суммы по исходному массиву
prefix_orig[0] = 0
для i от 1 до n:
    prefix_orig[i] = prefix_orig[i-1] + v[i-1]

// отсортированная копия + префиксные суммы по ней
u = копия v, отсортированная по неубыванию
prefix_sorted[0] = 0
для i от 1 до n:
    prefix_sorted[i] = prefix_sorted[i-1] + u[i-1]

прочитать m
повторить m раз:
    прочитать type, l, r
    если type == 1:
        вывести prefix_orig[r] - prefix_orig[l-1]
    иначе:
        вывести prefix_sorted[r] - prefix_sorted[l-1]

Код решения

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

Пример 1. $n=6$, $v=[6,4,2,7,2,7]$. Отсортированная копия $u=[2,2,4,6,7,7]$.

Пример 2. $n=4$, $v=[5,5,2,3]$, $u=[2,3,5,5]$, 10 запросов — все выходы совпали при ручном прогоне (см. таблицу в разделе «Разберём на примере» для первых четырёх; остальные шесть — 5, 5, 2, 12, 3, 5 — тоже подтверждены прямым вычитанием префиксных сумм на обоих массивах).

Все примеры условия сходятся.

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

1. $n = 1$ — единственный камень, префиксные суммы вырождаются в массив из двух элементов [0, v_1]; любой запрос l=r=1 даёт просто $v_1$ независимо от типа (сортировка одного элемента ничего не меняет).
2. Повторяющиеся значения стоимости — как в обоих примерах условия ($v_1=v_2=5$, $v_4=v_6=7$). Сортировка с повторами работает штатно, порядок одинаковых элементов между собой не важен для суммы диапазона.
3. Запрос на весь массив ($l=1, r=n$) — сумма по типу 1 и по типу 2 совпадает (это сумма всех элементов независимо от порядка), но вычисляется отдельно через свой префиксный массив — специальной оптимизации не требуется, оба пути дают одинаковый числовой результат.
4. Переполнение суммы. При $n = 10^5$ и $v_i$ до $10^9$ сумма всех элементов может достигать $10^{14}$ — далеко за пределами 32-битного int (до ~$2.1 \times 10^9$). В условии прямо указано на этот риск.

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

1. int вместо long long для сумм в C++. Суммарная стоимость всех камней легко достигает $10^{14}$ — переполнение int даст неверный (обычно отрицательный) ответ без явной ошибки времени выполнения.
2. Сортировать исходный массив вместо создания отдельной копии. Если отсортировать v "на месте", запросы типа 1 (про исходный порядок) станут отвечать неверно — нужно две отдельные структуры: исходный порядок и отсортированная копия.
3. Забыть про l - 1 при вычитании префиксной суммы. Формула суммы отрезка $[l, r]$ — это prefix[r] - prefix[l - 1], а не prefix[r] - prefix[l]; ошибка на единицу здесь выбрасывает из суммы либо на один элемент больше, либо на один меньше, чем нужно.
4. Быстрый ввод-вывод не настроен в C++. При $n, m$ до $10^5$ и посимвольном cin/cout без ios::sync_with_stdio(false) возможен вылет по времени — привычка отключать синхронизацию с stdio в начале main защищает от этого системно.

Сложность

Время: $O(n \log n)$ на сортировку и построение префиксных сумм, далее $O(1)$ на каждый из $m$ запросов — итого $O(n \log n + m)$. Память: $O(n)$ на оба префиксных массива.

---

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

Прорешай эти четыре задачи самостоятельно — все того же уровня CF ~1200, и все тренируют похожий стиль мышления: выразить ответ формулой или предвычислением вместо прямого перебора.

• Codeforces 1343C «Alternating Subsequence» (~CF 1200) — среди подпоследовательности знакопеременных по знаку чисел найти самую длинную, а среди самых длинных — с максимальной суммой элементов.
• Codeforces 977C «Less or Equal» (~CF 1200) — по заданному массиву и числу $k$ найти любое $x$ в диапазоне $[1, 10^9]$, для которого ровно $k$ элементов массива меньше или равны $x$, либо определить, что такого $x$ не существует.
• Codeforces 112B «Petya and Square» (~CF 1200) — по стороне квадрата $2n$ и координатам отмеченной клетки определить, можно ли разрезать квадрат ломаной линией по сетке на две равные (с точностью до поворота) части, не задевающие эту клетку.
• Codeforces 176A «Trading Business» (~CF 1200) — по ценам покупки и продажи товаров на разных планетах найти максимальную прибыль от одной сделки «купить на одной планете — продать на другой».

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

---

Что дальше

На следующей тренировке остаёмся на уровне CF ~1200–1300 и добавляем ещё два инструмента в связке: бинарный поиск по отсортированному массиву (не по ответу, а напрямую по значениям) и решето Эратосфена для быстрой проверки чисел на простоту.