1827F

不妨先考虑一个弱化版的问题，这个问题和原来的问题仅有一个区别：\(k\) 是给定整数。 称最后 \(n-k\) 个数是“特殊的”。那么我们可以注意到，每个特殊的数字的极大段必然递增放置或者递减放置。例如我们有排列 \([7,5,8,1,4,2,6,3]\) 而且 \(k=2\)，那么极大段的下标应该 ......

吓人题。 一个显然的想法是对于 $k$, 将贡献分为 $3$ 类 ：$[1,k]$ 子区间的贡献，$[k+1,n]$ 子区间的贡献和跨过 $k$ 的贡献。 首先 $[1,k]$ 的贡献我们可以沿用 Pudding Monsters 的做法，从左往右枚举 $r$，统计 $r$ 作为右端点的贡献。发现一 ......