题解

思路

对固定子数组 $a[l..r]$，最优方案中的排序区间可以取为互不相交。位置 $k$ 可以成为两个独立排序块之间的分界，当且仅当

因此该子数组的美丽值等于 $r-l$ 减去合法分界点的个数。先把所有子数组的 $r-l$ 求和，再统计每个合法分界的贡献。

做法

子任务 1

枚举 $l,r,k$，直接计算两侧最大值与最小值，复杂度 $O(n^4)$。

子任务 2

按右侧最小值所在位置 $i$ 统计贡献。令 $k$ 为 $i$ 左侧最近且满足 $a_k<a_i$ 的位置，$x$ 为 $k$ 左侧最近且满足 $a_x>a_i$ 的位置，$y$ 为 $i$ 右侧最近且满足 $a_y<a_i$ 的位置；不存在时使用边界 $0,n+1$。该位置贡献的合法分界数量为

逐位置线性扫描求 $x,k,y$，复杂度 $O(n^2)$。

满分算法

用单调栈在线性时间求每个 $i$ 的 $k$ 与 $y$。建立区间最大值稀疏表；从 $k$ 向左二进制跳跃，求出最后一个使区间最大值仍小于 $a_i$ 的边界，从而得到 $x$。答案初值为

再减去每个位置的 $(k-x)(y-i)$。

独立实现还可以按值从小到大激活位置，用两个有序集合维护已激活和未激活位置，并得到同一贡献式。

正确性证明

若两个排序操作相交，可用它们的并区间替代，代价不增加，所以存在由互不相交区间组成的最优方案。相邻两块能独立排序，当且仅当前块所有元素都小于后缀所有元素，等价于上述最大值小于最小值条件；每保留一个合法分界就比整体排序节省一秒。

对任意合法三元组 $(l,k,r)$，令 $a_i$ 是右段最小值。由互异性，$k$ 必为 $i$ 左侧最近的小于 $a_i$ 的位置，且恰有 $x<l\le k$、$i\le r<y$。反之这些范围内任取 $l,r$ 都满足分界条件，故位置 $i$ 恰贡献 $(k-x)(y-i)$ 个合法分界。算法枚举所有 $i$，无重无漏地减去全部节省量，因此答案正确。

复杂度

满分算法每个测试用例时间复杂度 $O(n\log n)$，空间复杂度 $O(n\log n)$；所有测试用例按 $\sum n$ 计。