P11987 题解

考虑把序列转成括号序列，每个值的第一个位置是左括号，第二个位置是右括号。

发现一种方案 $(x,y)$ 无解当且仅当 $x$ 和 $y$ 的括号对不交且 $y$ 在 $x$ 前面，也就是说，答案仅与不相交的括号对有关，而后者等价于每个左括号左边的右括号的出现次数之和。

考察一次交换操作，如果现在答案 $<n^2$ 那么必然存在右括号在左括号左边，也必然存在相邻的两个位置，左边是右括号，右边是左括号。交换它们可以使总数 $+1$，且不存在更优的方案。

按照最优的操作方式，每一步恰好使得总数 $+1$。这样我们就可以做了，用树状数组维护左括号和右括号的出现位置，动态修改即可。

我们求出的是使得交换之前总数为 $x$ 的最小代价 $f_x$，从小到大令 $f_x\leftarrow \min\{f_x,f_{x-1}+X\}$ 即可求出答案。

时间复杂度 $O(n\log n+m)$。