P11987 题解

lmh_qwq · 2025-04-02 16:37:09 · 题解

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

发现一种方案 (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)。