P1667

chenxia25 · 2021-08-30 11:25:18 · 题解

这种奇怪的在数列上操作，看看在前缀和 / 差分数组上发生了什么事往往能发现新大陆。

注意到这里选区间和，以及差分操作实际上是在前缀和数组上做单点操作，考虑 a​​​ 的前缀和 S​​​。那不难发现，这个操作其实就是让 S_{l-1}​​ 加上 S_r-S_{l-1}​，让 S_r​ 减去 S_r-S_{l-1}。那不就是交换 S_{l-1},S_r 呗！到这儿就比较好做了。

任意子序列和为正……那就是所有元素都为正呗。这当且仅当前缀和数组 S_1>0 且严格递增。如果 S 里面有 \leq 0 的值显然就废了，如果有两个相等的值无论如何不可能严格递增，那也废了。注意到这个交换操作是在 [1,n-1] 里交换，n 不能动。所以如果 S_n 不是最大那也废了，否则只需将 S_{1\sim n-1} 排序。

最小次数的话，其实就是任意排列变成恒等排列最小交换次数。建出有向图，数环的个数 c，答案就是 n-1-c。并查集或者 dfs 随便求。