Привет, Codeforces! На днях закончился длинный тур Открытой олимпиады этого года, который проходил с 21.11 по 15.01. В нём было много интересных задач, которые мне хотелось бы разобрать и обсудить в этом посте.↵
↵
Я постараюсь описать свои мысли в ходе решения как можно подробнее, но я не гарантирую, что начинающим спортпрогерам всё будет понятно ;)↵
↵
Собственно, ниже мои решения + реализации (прощу прощения, если код трудночитаем):↵
↵
<spoiler summary="А на 100 баллов">↵
Заметим тот факт, что для любого $1 < i \le n$ будет выполняться $max(p_{0:i}) \ge i$. Назовём _хорошей позицией_ такое $i$, что $max(p_{0:i}) = i$.↵
↵
Понятно, что если закончить очередной подотрезок не на _хорошей позиции_, то само число $i$ не войдет в этот подотрезок -> оно точно встретится в результирующей перестановке позже $max(p_{0:i})$, противоречие.↵
То есть, концы отрезков могут совпадать только с _хорошими позициями_ -> перестановку можно разбить на $k$ отрезков с необходимым свойством только тогда, когда количество _хороших позиций_ в этой перестановке $\ge k$.↵
Построение ответа достаточно тривиально — сделаем концами отрезков $k$ последних хороших позиций.↵
↵
Асимптотика: $O(n)$.↵
↵
Код: https://pastebin.com/05P67xen↵
</spoiler>↵
↵
<spoiler summary="B на 76 (100?) баллов">↵
Условие задачи можно переформулировать так — найти количество чисел $\le a_i$, таких, что сумма двух соседних цифр в их записи не превышает $10$. К этому можно придти кукареком (перебирая первые числа и находя закономерности) или через математику.↵
↵
В любом случае, переформулированную задачу можно решать с помощью ДП по цифрам, а именно по первой половине записи числа (потому что вторая половина будет зеркальна первой). Состоянием будет последняя рассмотренная позиция и цифра, которую на неё записали.↵
↵
Асимптотика: $O(log_{10}(a_i))$ для одного запроса.↵
↵
Код: https://pastebin.com/YrtJRZMG↵
</spoiler>↵
↵
<spoiler summary="C на 47 баллов">↵
В решениях ниже я буду считать, что $n = m$, поскольку в максимальных тестах это действительно так.↵
↵
Разобьём решение на 4 части: для групп 1-2, для группы 3, для группы 4 и для групп 4-5.↵
↵
Группы 1-2: запустим алгоритм Дейкстры на графе. На каждой итерации переберём ребро, исходящее из вершины, и если у него есть продолжение, то прорелаксируем все рёбра, достижимые из текущего по продолжениям. Иначе, релаксируем только рассмотренное ребро.↵
↵
Асимптотика: вроде бы $O(n^2 log n)$, но я не умею строго пруфать это.↵
↵
Группа 3: то же решение, что и для групп 1-2, но поскольку в этой группе рёбра не имеют продолжений, прийти к этому решению гораздо проще + асимптотика лучше.↵
↵
Асимптотика: $O(m log n)$.↵
↵
Группа 4: в этой группе можно написать 0-1 BFS (поскольку все ребра будут иметь вес либо 0, либо 1) или решение для группы 5.↵
↵
Асимптотика решения с 0-1 BFS: $O(n + m)$.↵
↵
Группа 5: представим, что вместо каждого ребра $v$ у нас есть $max(w) + 1$ его копий с весами от $0$ до $max(w)$. В таком случае, если приходим в $v$ из копии ребра $u$ с весом $x$, то:↵
↵
- $v$ является продолжением $u$ -> обновим ответ для копии $v$ с весом $max(0, x — 1)$↵
↵
- $v$ не является продолжением $u$ -> обновим ответ для копии $v$ с весом $w_v$↵
↵
Можем и здесь запустить Дейкстру, но нужно сделать важную оптимизацию, не перебирая те ребра, которые точно не можем прорелаксировать. А именно, если находясь в ребре $v$, мы не можем прорелаксировать хотя бы одно ребро, в которое можно придти из $v$ и которое не его продолжение, то мы аналогично не сможем прорелаксировать другие не-продолжения ребра $v$.↵
↵
Асимптотика: $O(m * max(w) * log(m))$.↵
↵
Код: https://pastebin.com/FXeBHdp1↵
</spoiler>↵
↵
<spoiler summary="D на 100 баллов">↵
В этой задаче существует масса вариаций с решениями на сетах, но я рассмотрю не совсем обычное, но более простое для меня решение с использованием техники _Segment Tree Beats_.↵
↵
Будем считать, что какая-то позиция обновлена в момент времени $x$, если после $x$-ой операции на ней появился снег, до $x$-ой операции на ней не было снега, и если этот снег не убрали до текущей операции. Если на позиции сейчас нет снега, то можно считать, что эта позиция была обновлена в момент $INF$.↵
↵
Будем хранить дерево отрезков с тремя параметрами для каждой вершины: _min_prev_time_, _max_prev_time_ и _total_time_, где _min_prev_time_ — минимальный момент времени, в который обновили какую-то позицию на отрезке; _max_prev_time_ — аналогично предыдущему, но на максимум; _total_time_ — сумма всех _total_time_ на этом отрезке.↵
↵
Если операция в момент времени $t$ имеет тип +, делаем min= $t$ для всех позиций с $l$ по $r$.↵
↵
Если операция в момент времени $t$ имеет тип -, делаем _total_time_ += $t$ — _prev_time_ и _prev_time_ = $INF$ для всех позиций с $l$ по $r$.↵
↵
Теперь определимся, какие-же tag/break условия нужно взять. Понятно, что делать min= $x$ на отрезке, на котором максимум меньше $x$, не имеет смысла, поэтому break-condition для операции +: _max_prev_time_ < $x$. Аналогично, tag-condition: _min_prev_time_ > $x$. ↵
↵
Break-condition для операции -: _min_prev_time_ == $INF$, tag-condition: _min_prev_time_ == _max_prev_time_.↵
↵
Строгого доказательства времени работы не будет, потому что не силён в методе потенциалов :( Буду очень рад, если кто-то в комментариях найдёт асимптотику данного решения.↵
↵
Код: https://pastebin.com/wy0REYfb↵
</spoiler>↵
↵
<spoiler summary="E на 67 (100?) баллов">↵
В этой задаче можно сделать корневую декомпозицию с идеей разбиения объектов по тяжести.↵
↵
Скажем, что число $x$ является тяжелым, если оно встречается $\ge k$ раз в массиве. Отсюда понятно, что тяжёлых чисел не больше $n / k$.↵
↵
Предподсчитаем ответ для всех различных пар чисел в массиве, в которых есть хотя бы одно тяжелое число. Понятно, что таких пар будет не больше $n * (n / k)$. Это можно сделать одним проходом по массиву, храня для каждого тяжелого числа количество уже рассмотренных его копий. Асимптотика: $O(n * (n / k))$.↵
↵
После предподсчета начнем обрабатывать запросы. Если в текущем запросе нет ни одного тяжелого числа, можно найти ответ методом указателей за $O(k)$. Иначе, мы уже посчитали ответ в предподсчете.↵
↵
Таким образом, получаем сложность решения $O(n * (n / k) + q * k)$. Если предположить, что $n = q$, то выгоднее всего будет взять $k = \sqrt{n}$, получим $O((n + q) * sqrt(n))$.↵
↵
Код: https://pastebin.com/mtazYBZW↵
</spoiler>↵
↵
<spoiler summary="F на 76 (100?) баллов">↵
Первые 4 группы достаточно легко сдаются склейкой различных простых идей, мы же приступим сразу к 5 группе.↵
↵
Есть один интересный способ проверки на то, является ли отрезок статической строки ПСП. А именно, если посчитать стеки для всех префиксов строки, то $[l; r]$ будет являться ПСП тогда и только тогда, когда стеки для префиксов $[0; l - 1]$ и $[0; r]$ равны. Разумеется, сравнивать стеки поэлементно очень долго, поэтому захешируем их.↵
↵
Получаем решение для 5 группы, которое работает за $O(n + q)$.↵
↵
В 6 группе всё уже не так просто, поскольку появляются изменения в точке. Если мы хотим и дальше использовать хеширование в решении, то полиномальное нам точно не подойдет, поскольку наше хеширование должно быть ассоциативным (чтобы не считать хеш поэлементно) и некоммутативно (чтобы порядок элементов имел значение). Вспоминаем, что умножение матриц выполняет оба этих свойства! ↵
↵
Значит, можно каждой открытой скобке сопоставить матрицу 2x2 из случайных чисел от $0$ до $MOD - 1$, а каждой закрытой скобке — матрицу, обратную матрице открытой скобки такого же типа. В таком случае, если подотрезок является ПСП, то произведение матриц на нём является единичной матрицей.↵
↵
Чтобы добавить обновления в точке, построим дерево отрезков с операцией умножения матриц, обновление в таком случае делается тривиально.↵
↵
Взломать такой хеш невероятно трудно (поскольку существует порядка $MOD^(d^2) / 2$ различных пар матриц (где $d$ — сторона матрицы), произведение которых равно единичной матрице, причем каждая матрица имеет только одну матрицу-пару).↵
↵
Итоговая асимптотика: $O(d^3 * n * log(n))$, где $d$ — выбранный размер матрицы для хеширования.↵
↵
Код: https://pastebin.com/r71qkqzT↵
</spoiler>↵
↵
<spoiler summary="G на 100 баллов">↵
Определим ПСП немного иначе: ПСП называется такая строка, что для любого $0 \le i < n$ на суффиксе $[i:n]$ находится ровно $(n - i) / 2$ открытых скобок (поскольку при большем или меньшем количестве не будет подходящего баланса).↵
↵
Из этого определения гораздо легче вывести жадное решение задачи.↵
↵
Будем рассматривать все позиции по уменьшению их стоимости и параллельно для каждой позиции хранить количество открытых скобок, которое мы можем поставить на суффиксе этой позиции. Если текущая позиция — p и на префиксе $[0:p + 1]$ мы в любую позицию ещё можем поставить одну открытую скобку, сделаем это и обновим количества на префиксе. Если же не можем сделать, то переходим к следующей позиции.↵
↵
Для поддерживания количеств открытых скобок, которые можем поставить на суффиксе, удобнее всего использовать дерево отрезков на массовые операции. Получаем решение с асимптотикой $O(n log n)$.↵
↵
Получившееся решение отдалённо напоминает алгоритм построение миностова. Однако, я не умею строго доказывать корректность этого алгоритма, то есть это кукарек (впрочем, как и в большинстве жадных решений ;)).↵
↵
Код: https://pastebin.com/fHn6Nt2S↵
</spoiler>↵
↵
<spoiler summary="H на 79 (100?) баллов">↵
Переформулируем задачу в более формальный вид. Обозначим за $f(l, r)$ ответ для отрезка $[l; r]$. В таком случае, если $a_l \ne a_r$, нетрудно доказать, что $f(l, r) = max(f(l + 1, r) + 1, a_{r - 1} - a_l)$ (случай $a_l == a_r$ тривиален).↵
↵
Эту же формулу можно представить немного в другом виде. Для каждого $p$ в массиве $nx$ будем хранить самую правую позицию массива, число на которой равно $a_p$. Пусть $x = nx_l$, $s = (a_r - a_l) + (nx_l - l)$. Пока $a_x \ne a_r$, будем "прыгать" через блок равных элементов ($x = nx_{x + 1}$), изменяя текущий баланс (прибавляя разницу между новым и старым значением, вычитая длину блока). В те моменты, когда баланс будет меньше $0$, будем вычитать его из $s$ и делать снова равным $0$. Доказательство корректности перехода от $f(l, r)$ к этому алгоритму я оставляю читателю.↵
↵
Итак, у нас уже есть достаточно быстрый алгоритм, который получает 76 баллов. Чтобы получить полный балл, можно заметить, что можно построить прыжки через прыжки через блоки равных чисел. А именно, из каждого момента, в котором у нас нулевой баланс, мы будем прыгать в ближайший момент с отрицательным балансом, обновляя ответ и снова приходя в момент с нулевым балансом.↵
↵
Однако и этого мало, потому что у нас может быть очень много таких моментов. Поэтому, на новых прыжках мы построим бинапы на сумму, а чтобы построить их, пройдемся по блокам равных элементов с деревом отрезков.↵
↵
Получившееся решение работает за $O((n + q) log n)$.↵
↵
Код: https://pastebin.com/HTC0WgSf↵
</spoiler>↵
↵
<spoiler summary="I на 82 балла + некоторые идеи на 100 баллов">↵
Пусть pr — массив простых чисел, где $pr_0 = 2, pr_1 = 3$ etc.↵
↵
Нам нужно найти $f(n, b)$, где $f(x, y) = x$ при $x < pr_y$. ↵
Функцию можно вычислять по следующей формуле: $f(n, b) = f(n, b - 1) + f(n / pr[b], b - 1) + ... + f(n / (pr[b]^k), b - 1)$, где $k = floor(log_{pr_b}(n))$.↵
↵
Далее можно заметить, что значения $f(n, b)$ при достаточно маленьких ($\le 2000000$) $n$ будут использоваться очень часто, поэтому эти значения можно запомнить в массиве и не пересчитывать много раз. Помимо этого, для $b \le 8$ (или 9) будет не так много различных чисел, которые в разложении содержат множители не больше $pr_b$ (а именно, порядка пары десятков миллионов), а значит, все эти числа можно также сохранить в отсортированном массиве и при маленьких b вместо запуска функции находить ответ lower_bound-ом к этому массиву).↵
↵
Совокупность этих идей при аккуратной реализации даёт 82 балла.↵
↵
Идеи на 100: заметим, что $f(n, b) = f(n, b - 1) + f(n / pr[b], b)$ (это очевидно вытекает из прошлой формулы), то есть, можно вычислять значения функции не в глубину, а в ширину. Если прикрутить различные оптимизации к стандартному алгоритму BFS, получится решение, которое на максимальном тесте работает около 3.6 секунд, чего достаточно для получения 100 баллов. ↵
↵
Вышеописанной идеей со мной поделился [user:grishared,2023-01-16], за что я ему крайне признателен.↵
↵
Код: https://pastebin.com/LzZNhtJq↵
</spoiler>↵
↵
Спасибо за внимание!
↵
Я постараюсь описать свои мысли в ходе решения как можно подробнее, но я не гарантирую, что начинающим спортпрогерам всё будет понятно ;)↵
↵
Собственно, ниже мои решения + реализации (прощу прощения, если код трудночитаем):↵
↵
<spoiler summary="А на 100 баллов">↵
Заметим тот факт, что для любого $1 < i \le n$ будет выполняться $max(p_{0:i}) \ge i$. Назовём _хорошей позицией_ такое $i$, что $max(p_{0:i}) = i$.↵
↵
Понятно, что если закончить очередной подотрезок не на _хорошей позиции_, то само число $i$ не войдет в этот подотрезок -> оно точно встретится в результирующей перестановке позже $max(p_{0:i})$, противоречие.↵
То есть, концы отрезков могут совпадать только с _хорошими позициями_ -> перестановку можно разбить на $k$ отрезков с необходимым свойством только тогда, когда количество _хороших позиций_ в этой перестановке $\ge k$.↵
Построение ответа достаточно тривиально — сделаем концами отрезков $k$ последних хороших позиций.↵
↵
Асимптотика: $O(n)$.↵
↵
Код: https://pastebin.com/05P67xen↵
</spoiler>↵
↵
<spoiler summary="B на 76 (100?) баллов">↵
Условие задачи можно переформулировать так — найти количество чисел $\le a_i$, таких, что сумма двух соседних цифр в их записи не превышает $10$. К этому можно придти кукареком (перебирая первые числа и находя закономерности) или через математику.↵
↵
В любом случае, переформулированную задачу можно решать с помощью ДП по цифрам, а именно по первой половине записи числа (потому что вторая половина будет зеркальна первой). Состоянием будет последняя рассмотренная позиция и цифра, которую на неё записали.↵
↵
Асимптотика: $O(log_{10}(a_i))$ для одного запроса.↵
↵
Код: https://pastebin.com/YrtJRZMG↵
</spoiler>↵
↵
<spoiler summary="C на 47 баллов">↵
В решениях ниже я буду считать, что $n = m$, поскольку в максимальных тестах это действительно так.↵
↵
Разобьём решение на 4 части: для групп 1-2, для группы 3, для группы 4 и для групп 4-5.↵
↵
Группы 1-2: запустим алгоритм Дейкстры на графе. На каждой итерации переберём ребро, исходящее из вершины, и если у него есть продолжение, то прорелаксируем все рёбра, достижимые из текущего по продолжениям. Иначе, релаксируем только рассмотренное ребро.↵
↵
Асимптотика: вроде бы $O(n^2 log n)$, но я не умею строго пруфать это.↵
↵
Группа 3: то же решение, что и для групп 1-2, но поскольку в этой группе рёбра не имеют продолжений, прийти к этому решению гораздо проще + асимптотика лучше.↵
↵
Асимптотика: $O(m log n)$.↵
↵
Группа 4: в этой группе можно написать 0-1 BFS (поскольку все ребра будут иметь вес либо 0, либо 1) или решение для группы 5.↵
↵
Асимптотика решения с 0-1 BFS: $O(n + m)$.↵
↵
Группа 5: представим, что вместо каждого ребра $v$ у нас есть $max(w) + 1$ его копий с весами от $0$ до $max(w)$. В таком случае, если приходим в $v$ из копии ребра $u$ с весом $x$, то:↵
↵
- $v$ является продолжением $u$ -> обновим ответ для копии $v$ с весом $max(0, x — 1)$↵
↵
- $v$ не является продолжением $u$ -> обновим ответ для копии $v$ с весом $w_v$↵
↵
Можем и здесь запустить Дейкстру, но нужно сделать важную оптимизацию, не перебирая те ребра, которые точно не можем прорелаксировать. А именно, если находясь в ребре $v$, мы не можем прорелаксировать хотя бы одно ребро, в которое можно придти из $v$ и которое не его продолжение, то мы аналогично не сможем прорелаксировать другие не-продолжения ребра $v$.↵
↵
Асимптотика: $O(m * max(w) * log(m))$.↵
↵
Код: https://pastebin.com/FXeBHdp1↵
</spoiler>↵
↵
<spoiler summary="D на 100 баллов">↵
В этой задаче существует масса вариаций с решениями на сетах, но я рассмотрю не совсем обычное, но более простое для меня решение с использованием техники _Segment Tree Beats_.↵
↵
Будем считать, что какая-то позиция обновлена в момент времени $x$, если после $x$-ой операции на ней появился снег, до $x$-ой операции на ней не было снега, и если этот снег не убрали до текущей операции. Если на позиции сейчас нет снега, то можно считать, что эта позиция была обновлена в момент $INF$.↵
↵
Будем хранить дерево отрезков с тремя параметрами для каждой вершины: _min_prev_time_, _max_prev_time_ и _total_time_, где _min_prev_time_ — минимальный момент времени, в который обновили какую-то позицию на отрезке; _max_prev_time_ — аналогично предыдущему, но на максимум; _total_time_ — сумма всех _total_time_ на этом отрезке.↵
↵
Если операция в момент времени $t$ имеет тип +, делаем min= $t$ для всех позиций с $l$ по $r$.↵
↵
Если операция в момент времени $t$ имеет тип -, делаем _total_time_ += $t$ — _prev_time_ и _prev_time_ = $INF$ для всех позиций с $l$ по $r$.↵
↵
Теперь определимся, какие-же tag/break условия нужно взять. Понятно, что делать min= $x$ на отрезке, на котором максимум меньше $x$, не имеет смысла, поэтому break-condition для операции +: _max_prev_time_ < $x$. Аналогично, tag-condition: _min_prev_time_ > $x$. ↵
↵
Break-condition для операции -: _min_prev_time_ == $INF$, tag-condition: _min_prev_time_ == _max_prev_time_.↵
↵
Строгого доказательства времени работы не будет, потому что не силён в методе потенциалов :( Буду очень рад, если кто-то в комментариях найдёт асимптотику данного решения.↵
↵
Код: https://pastebin.com/wy0REYfb↵
</spoiler>↵
↵
<spoiler summary="E на 67 (100?) баллов">↵
В этой задаче можно сделать корневую декомпозицию с идеей разбиения объектов по тяжести.↵
↵
Скажем, что число $x$ является тяжелым, если оно встречается $\ge k$ раз в массиве. Отсюда понятно, что тяжёлых чисел не больше $n / k$.↵
↵
Предподсчитаем ответ для всех различных пар чисел в массиве, в которых есть хотя бы одно тяжелое число. Понятно, что таких пар будет не больше $n * (n / k)$. Это можно сделать одним проходом по массиву, храня для каждого тяжелого числа количество уже рассмотренных его копий. Асимптотика: $O(n * (n / k))$.↵
↵
После предподсчета начнем обрабатывать запросы. Если в текущем запросе нет ни одного тяжелого числа, можно найти ответ методом указателей за $O(k)$. Иначе, мы уже посчитали ответ в предподсчете.↵
↵
Таким образом, получаем сложность решения $O(n * (n / k) + q * k)$. Если предположить, что $n = q$, то выгоднее всего будет взять $k = \sqrt{n}$, получим $O((n + q) * sqrt(n))$.↵
↵
Код: https://pastebin.com/mtazYBZW↵
</spoiler>↵
↵
<spoiler summary="F на 76 (100?) баллов">↵
Первые 4 группы достаточно легко сдаются склейкой различных простых идей, мы же приступим сразу к 5 группе.↵
↵
Есть один интересный способ проверки на то, является ли отрезок статической строки ПСП. А именно, если посчитать стеки для всех префиксов строки, то $[l; r]$ будет являться ПСП тогда и только тогда, когда стеки для префиксов $[0; l - 1]$ и $[0; r]$ равны. Разумеется, сравнивать стеки поэлементно очень долго, поэтому захешируем их.↵
↵
Получаем решение для 5 группы, которое работает за $O(n + q)$.↵
↵
В 6 группе всё уже не так просто, поскольку появляются изменения в точке. Если мы хотим и дальше использовать хеширование в решении, то полиномальное нам точно не подойдет, поскольку наше хеширование должно быть ассоциативным (чтобы не считать хеш поэлементно) и некоммутативно (чтобы порядок элементов имел значение). Вспоминаем, что умножение матриц выполняет оба этих свойства! ↵
↵
Значит, можно каждой открытой скобке сопоставить матрицу 2x2 из случайных чисел от $0$ до $MOD - 1$, а каждой закрытой скобке — матрицу, обратную матрице открытой скобки такого же типа. В таком случае, если подотрезок является ПСП, то произведение матриц на нём является единичной матрицей.↵
↵
Чтобы добавить обновления в точке, построим дерево отрезков с операцией умножения матриц, обновление в таком случае делается тривиально.↵
↵
Взломать такой хеш невероятно трудно (поскольку существует порядка $MOD^(d^2) / 2$ различных пар матриц (где $d$ — сторона матрицы), произведение которых равно единичной матрице, причем каждая матрица имеет только одну матрицу-пару).↵
↵
Итоговая асимптотика: $O(d^3 * n * log(n))$, где $d$ — выбранный размер матрицы для хеширования.↵
↵
Код: https://pastebin.com/r71qkqzT↵
</spoiler>↵
↵
<spoiler summary="G на 100 баллов">↵
Определим ПСП немного иначе: ПСП называется такая строка, что для любого $0 \le i < n$ на суффиксе $[i:n]$ находится ровно $(n - i) / 2$ открытых скобок (поскольку при большем или меньшем количестве не будет подходящего баланса).↵
↵
Из этого определения гораздо легче вывести жадное решение задачи.↵
↵
Будем рассматривать все позиции по уменьшению их стоимости и параллельно для каждой позиции хранить количество открытых скобок, которое мы можем поставить на суффиксе этой позиции. Если текущая позиция — p и на префиксе $[0:p + 1]$ мы в любую позицию ещё можем поставить одну открытую скобку, сделаем это и обновим количества на префиксе. Если же не можем сделать, то переходим к следующей позиции.↵
↵
Для поддерживания количеств открытых скобок, которые можем поставить на суффиксе, удобнее всего использовать дерево отрезков на массовые операции. Получаем решение с асимптотикой $O(n log n)$.↵
↵
Получившееся решение отдалённо напоминает алгоритм построение миностова. Однако, я не умею строго доказывать корректность этого алгоритма, то есть это кукарек (впрочем, как и в большинстве жадных решений ;)).↵
↵
Код: https://pastebin.com/fHn6Nt2S↵
</spoiler>↵
↵
<spoiler summary="H на 79 (100?) баллов">↵
Переформулируем задачу в более формальный вид. Обозначим за $f(l, r)$ ответ для отрезка $[l; r]$. В таком случае, если $a_l \ne a_r$, нетрудно доказать, что $f(l, r) = max(f(l + 1, r) + 1, a_{r - 1} - a_l)$ (случай $a_l == a_r$ тривиален).↵
↵
Эту же формулу можно представить немного в другом виде. Для каждого $p$ в массиве $nx$ будем хранить самую правую позицию массива, число на которой равно $a_p$. Пусть $x = nx_l$, $s = (a_r - a_l) + (nx_l - l)$. Пока $a_x \ne a_r$, будем "прыгать" через блок равных элементов ($x = nx_{x + 1}$), изменяя текущий баланс (прибавляя разницу между новым и старым значением, вычитая длину блока). В те моменты, когда баланс будет меньше $0$, будем вычитать его из $s$ и делать снова равным $0$. Доказательство корректности перехода от $f(l, r)$ к этому алгоритму я оставляю читателю.↵
↵
Итак, у нас уже есть достаточно быстрый алгоритм, который получает 76 баллов. Чтобы получить полный балл, можно заметить, что можно построить прыжки через прыжки через блоки равных чисел. А именно, из каждого момента, в котором у нас нулевой баланс, мы будем прыгать в ближайший момент с отрицательным балансом, обновляя ответ и снова приходя в момент с нулевым балансом.↵
↵
Однако и этого мало, потому что у нас может быть очень много таких моментов. Поэтому, на новых прыжках мы построим бинапы на сумму, а чтобы построить их, пройдемся по блокам равных элементов с деревом отрезков.↵
↵
Получившееся решение работает за $O((n + q) log n)$.↵
↵
Код: https://pastebin.com/HTC0WgSf↵
</spoiler>↵
↵
<spoiler summary="I на 82 балла + некоторые идеи на 100 баллов">↵
Пусть pr — массив простых чисел, где $pr_0 = 2, pr_1 = 3$ etc.↵
↵
Нам нужно найти $f(n, b)$, где $f(x, y) = x$ при $x < pr_y$. ↵
Функцию можно вычислять по следующей формуле: $f(n, b) = f(n, b - 1) + f(n / pr[b], b - 1) + ... + f(n / (pr[b]^k), b - 1)$, где $k = floor(log_{pr_b}(n))$.↵
↵
Далее можно заметить, что значения $f(n, b)$ при достаточно маленьких ($\le 2000000$) $n$ будут использоваться очень часто, поэтому эти значения можно запомнить в массиве и не пересчитывать много раз. Помимо этого, для $b \le 8$ (или 9) будет не так много различных чисел, которые в разложении содержат множители не больше $pr_b$ (а именно, порядка пары десятков миллионов), а значит, все эти числа можно также сохранить в отсортированном массиве и при маленьких b вместо запуска функции находить ответ lower_bound-ом к этому массиву).↵
↵
Совокупность этих идей при аккуратной реализации даёт 82 балла.↵
↵
Идеи на 100: заметим, что $f(n, b) = f(n, b - 1) + f(n / pr[b], b)$ (это очевидно вытекает из прошлой формулы), то есть, можно вычислять значения функции не в глубину, а в ширину. Если прикрутить различные оптимизации к стандартному алгоритму BFS, получится решение, которое на максимальном тесте работает около 3.6 секунд, чего достаточно для получения 100 баллов. ↵
↵
Вышеописанной идеей со мной поделился [user:grishared,2023-01-16], за что я ему крайне признателен.↵
↵
Код: https://pastebin.com/LzZNhtJq↵
</spoiler>↵
↵
Спасибо за внимание!
