Заметим тот факт, что для любого 1 < i <= n будет выполняться max(p[0:i]) >= i. Назовём "хорошей позицией" такое i, что max(p[0:i]) = i.

Понятно, что если закончить очередной подотрезок не на хорошей позиции, то само число i не войдет в этот подотрезок -> оно точно встретится в результирующей перестановке позже max(p[0:i]), противоречие. То есть, концы отрезков могут совпадать только с хорошими позициями -> перестановку можно разбить на k отрезков с необходимым свойством только тогда, когда количество хороших позиций в этой перестановке >= k. Построение ответа достаточно тривиально — сделаем концами отрезков k последних хороших позиций.

Асимптотика — O(n).

Условие задачи можно переформулировать так — найти количество чисел <= a[i], таких, что сумма двух соседних цифр в их записи не превышает 10. К этому можно придти кукареком (перебирая первые числа и находя закономерности) или через математику.

В любом случае, переформулированную задачу можно решать с помощью ДП по цифрам, а именно по первой половине записи числа (потому что вторая половина будет зеркальна первой). Состоянием будет последняя рассмотренная позиция и цифра, которую на неё записали.

Асимптотика: O(log10(a[i])) для одного запроса.

В решениях ниже я буду считать, что 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)).

В этой задаче существует масса вариаций с решениями на сетах, но я рассмотрю не совсем обычное, но более простое для меня решение с использованией техники 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.

Строгого доказательства времени работы не будет, потому что не силён в методе потенциалов :( Буду очень рад, если кто-то в комментариях найдёт асимптотику данного решения.

В этой задаче можно сделать корневую декомпозицию с идеей разбиения объектов по тяжести.

Скажем, что число x является тяжелым, если оно встречается >= 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)).

Первые 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 — выбранный размер матрицы для хеширования.

Определим ПСП немного иначе: ПСП называется такая строка, что для любого 0 <= i < n на суффиксе [i:n] находится ровно (n — i) / 2 открытых скобок (поскольку при большем или меньшем количестве не будет подходящего баланса).

Из этого определения гораздо легче вывести жадное решение задачи.

Будем рассматривать все позиции по уменьшению их стоимости и параллельно для каждой позиции хранить количество открытых скобок, которое мы можем поставить на суффиксе этой позиции. Если текущая позиция — p и на префиксе [0:p + 1] мы в любую позицию ещё можем поставить одну открытую скобку, сделаем это и обновим количества на префиксе. Если же не можем сделать, то переходим к следующей позиции.

Для поддерживания количеств открытых скобок, которые можем поставить на суффиксе, удобнее всего использовать дерево отрезков на массовые операции. Получаем решение с асимптотикой O(n log n).

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