Идея (две варианта):

1. Брутфорс (простое и понятно). Перебираем все пары (l,r) (O(n²)), считаем суммы префиксами — при расчёте сумм через префиксы сложность O(n²). Для маленьких ограничений проходит.

2. Конструктив (быстро и красиво). Наблюдение: корректное разбиение либо даёт все три суммы равными, либо разные попарно. Можно проверить, существует ли вообще решение по сумме массива (например, sum % 3 == 0). Если конструкция возможна, простой выбор границ l = 1, r = n-1 часто даёт валидное разбиение. Если по проверкам разбиение невозможно — выводим 0 0.

Алгоритм (кратко): Вычислить префикс суммы. Если есть очевидная проверка невозможности — вернуть 0 0. Иначе вернуть заранее выбранные границы или найти корректные за O(n) перебором левого края.

Сложность: O(n) — O(n²) в зависимости от проверки; брутфорс — O(n²) с префиксами.

Идея (интуиция): Нужно сделать как можно больше элементов «не на своём месте» по сравнению с отсортированным вариантом. Нули можно заменить на отсутствующие элементы так, чтобы они оказались максимально вне своих целевых индексов.

Подход:

1. Построить отсортированную версию массива (целевая позиция для каждого значения).
2. Собрать все отсутствующие в исходном элементы — кандидаты для подстановки в нули. Лучше брать наибольшие отсутствующие.
3. Заполнить нули этими значениями.
4. После замены задача сводится к поиску максимальной длины отрезка, в котором a[i] != target_pos_of(a[i]). Это решается двумя указателями: расширяем правый, пока условие выполняется, при нарушении сдвигаем левый.

Сложность: сортировка + двухуказатель → O(n log n).

Замечания: аккуратно работать с множественными одинаковыми значениями и индексированием в отсортированном массиве (использовать multimap/вектор позиций).

Идея (динамика по позиции и состоянию swap): На каждом индексе можно либо сделать swap между a[i] и b[i], либо не делать. Включение индекса в хорошее множество зависит от соседних сравнений. Поэтому держим два состояния для позиции i:

dp[i][0] — количество способов (или достижимость), если на i не сделали swap. dp[i][1] — если на i сделали swap.

Переходы (условия): Чтобы перейти в dp[i][1], нужно, сравнив с i-1, чтобы условия после и перед swap'ов выполнялись: — если и на i-1 была swap: b[i-1] <= a[i] и a[i-1] <= b[i] — если на i-1 не было swap: a[i-1] <= a[i] и b[i-1] <= b[i] Аналогичные проверки для dp[i][0].

Таким образом на каждом i обновляем dp[i][0] и dp[i][1] суммируя допустимые переходы из i-1. Не забываем про модуль, если нужно считать числа способов.

Сложность: O(n) по времени и O(1) по памяти (храним только предыдущий слой).

Идея (группировка + префикс частот): Если фиксировать d, итоговые значения группируются по диапазонам длины d: [1..d], [d+1..2d], ... Для каждого диапазона все числа переходят в одно значение (value_level).

Алгоритм:

1. Посчитать частоты каждого числа до mx = max(a).
2. Построить префикс частот pref, чтобы быстро получить количество элементов в любом числовом диапазоне [L..R] как pref[R] — pref[L-1].
3. Для каждого d от 1 до mx: — Итерируем по диапазонам длины d: [1..d], [d+1..2d], ... — Через pref получаем количество элементов cnt в каждом диапазоне. — Вычисляем вклад диапазона в итоговую сумму: cnt * value_level (value_level = (R)/d округлённо вверх или по нужной формуле). — Если есть лишние элементы, которые нельзя покрыть (d — cnt), учитываем штраф/уменьшение.
4. Для каждого d суммируем вклад по всем диапазонам и обновляем максимум.

Почему это быстро: суммарно для всех d работа примерно mx * (1 + 1/2 + 1/3 + ...) = mx * log(mx).

Сложность: ~ O(mx * log mx), где mx = max(a), с O(mx) памяти на частоты и префиксы.

Замечания: аккуратно работать с границами диапазонов, округлением вверх и пустыми диапазонами.