Автор и разработчик задачи: Ильдар Гайнуллин
Нам нужно разделить перестановку на несколько подотрезков, минимизировав их суммарную стоимость. Цена одного подотрезка равна $$$x$$$ плюс количество инверсий на этом подотрезке.
Обозначим количество инверсий на отрезке за $$$f_{l,r}$$$.
Заметим, что $$$f_{l,r} = f_{l+1, r} + f_{l,r-1} - f_{l+1,r-1} + (1$$$, если $$$p_l > p_r)$$$.
Значит, $$$f_{l,r} + f_{l+1,r-1} \geq f_{l+1,r} + f_{l,r-1}$$$, поэтому мы можем воспользоваться некоторыми оптимизациями ДП для решения этой задачи.
Будем оптимизировать $$$dp_i = \min{(dp_j + f_{j+1,i})}$$$.
Будем вычислять это ДП, используя метод Разделяй и властвуй.
Для начала, вычислим значения ДП для состояний $$$1,\ldots,\frac{n}{2}$$$ (рекурсивно).
Затем, нужно произвести пересчет значений $$$j > \frac{n}{2}$$$ через значения $$$i \leq \frac{n}{2}$$$. И затем, нужно будет рекурсивно вычислить значения для состояний $$$\frac{n}{2}+1,\ldots,n$$$.
Обратите внимание, что благодаря свойству нашей функции, оптимальное $$$i$$$ $$$\leq \frac{n}{2}$$$ для $$$j$$$ — монотонно возрастает при возрастании $$$j$$$.
Поэтому, можно воспользоваться методом Разделяй и властвуй для монотонных функций. Сначала найдем оптимальную точку для $$$i = \frac{(l+r)}{2}$$$ и затем рекурсивно разобьемся на две половины.
Но как вычислить $$$f_{l,r}$$$?
Во время Разделяй и властвуй, нам нужно будет переместить $$$l$$$ и $$$r$$$ только $$$\mathcal{O}{(n \log n)}$$$ раз суммарно. Поэтому, мы можем поддерживать $$$f_{l,r}$$$ и изменять его, когда нам нужно увеличить/уменьшить $$$l$$$/$$$r$$$. Это можно сделать с помощью дерева Фенвика, получив решение за очень быстрый $$$\mathcal{O}{(n \log^3 n)}$$$.
Также, можно предподсчитать некоторую информацию, используя SQRT декомпозицию. Можно заметить, что наши запросы выражаются через запросы вида «найти количество чисел $$$\leq x$$$ на отрезке $$$l \ldots r$$$». Используя sqrt декомпозицию, мы можем отвечать на эти запросы за $$$\mathcal{O}{(1)}$$$ с предподсчетом за $$$\mathcal{O}{(n \sqrt n)}$$$, в итоге получится решение за $$$\mathcal{O}{(n \log^2 n + n \sqrt{n})}$$$.