题解

思路

把从位置 $i$ 开始操作后的排列记为 $Q_i$。

做法

升序排序一个窗口不可能让排列比原排列字典序更大；如果原排列中存在长度至少为 $K$ 的严格递增连续段，就能选择其中一个窗口而保持 $P$ 不变，此时答案就是 $P$。否则，最后一个窗口的起点 $r=N-K+1$ 至少能保留前 $N-K$ 个元素，所以最优操作也必须保留这段前缀。

考虑更靠左的起点 $i<r$。它能保留上述前缀，当且仅当 $P_i,\ldots,P_{r-1}$ 已严格递增，并且窗口中新加入的 $P_r,\ldots,P_{i+K-1}$ 全都大于 $P_{r-1}$。可从 $r-1$ 向左找到最长递增段的左端点，再检查允许范围内最小的候选 $i$；若它合法，排序的后缀前缀最短，所得排列字典序最大，否则只能选择 $r$。最后只需对选中的一个长度为 $K$ 的窗口排序。

复杂度

扫描为 $O(N)$，排序为 $O(K\log K)$，总复杂度 $O(N\log N)$，空间复杂度 $O(N)$。