题解

思路

固定序列 $A$ 并从大到小考虑写入的值。

做法

第一个位置一定新开一次操作；对 $i>1$，只有当存在 $j<i$，满足 $A_j=A_i$ 且 $j,i$ 之间的所有数都严格大于 $A_i$ 时，位置 $i$ 才能并入此前同值位置对应的区间操作而不增加次数。这样的可并入关系对每个位置唯一，所以可以先把所有 $N M^N$ 次位置贡献全部计入，再减去所有可并入情形。

令端点距离为 $d=i-j$、共同值为 $x$。中间 $d-1$ 个数有 $(M-x)^{d-1}$ 种选择，区间外有 $M^{N-d-1}$ 种，距离为 $d$ 的端点对有 $N-d$ 个。因此答案为 $NM^N-\sum_{d=1}^{N-1}(N-d)M^{N-d-1}\sum_{x=1}^{M}(M-x)^{d-1}$。

复杂度

预处理 $M$ 的幂，并对每个 $b=M-x$ 依次维护 $b^{d-1}$，即可在 $O(NM)$ 时间和 $O(N)$ 空间内完成计算。