区间排序（简单版）题解

思路

对一个数组，某条相邻边界会贡献 1 秒，当且仅当存在一个逆序对跨过这条边界。所有被逆序对跨过的边界可以按连续段分别排序，总费用就是这些边界的数量；反过来，每个逆序对的两个端点必须被某次排序连接，因此这些边界都不可避免。

于是对子数组 $[l,r]$，边界 $i$ 有贡献当且仅当

交换求和顺序：固定原数组中的边界 $i$，统计有多少对端点 $(l,r)$ 满足上式。

做法

固定边界 $i$。向右预处理从 $i+1$ 开始的前缀最小值；再令 $l$ 从 $i$ 向左移动，同时维护 $[l,i]$ 的最大值。左侧最大值单调不降，右侧前缀最小值单调不升，因此第一个满足“小于左侧最大值”的右端点只会向左移动，可以用一个指针线性扫描。

把每个 $l$ 对应的合法右端点数量加入答案。对所有边界执行这一过程。

复杂度

每条边界线性扫描左右两侧，总时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。