ARC204B Sort Permutation

那我问你。

首先考虑这个最小操作次数是啥。我们将 $i \to p_i$ 连一条边，形成若干个环，设环数为 $r$，则为 $n - r$。每个环是独立的，方案就是每次选择一条边 $u \to v$，将 $v$ 从环上删掉，若原来 $v \to w$ 则新的环上 $u \to w$。这样每次操作能归位一个。直到 $u \to v$ 和 $v \to u$ 形成了二元环，仅需一次操作。

考虑最大化得分，即 $u \equiv v \pmod n$ 的次数。我们发现环可以随意断掉一条边变成一个链，会发现这样是不会使答案减小的。假设一对点要通过这条边产生贡献，那么可以在另一边先把环缩掉，使用另一条边。于是我们拍平成一条链，把链上每个点重标号一下变成 $1 \to 2 \to \cdots \to m$，设第 $i$ 个点原来的标号是 $a_i$。删点的形式容易考虑一个区间 DP。设 $f_{l, r}$ 表示从 $l$ 到 $r$ 的这条链上删点，最后仅剩了 $l$ 的答案。转移枚举中点 $mid$，有 $f_{l, r} \gets f _ {l, mid - 1} + f _ {mid, r} + [a_l \equiv a_{mid} \pmod n]$。那么 $f_{1, m}$ 即为答案。

这样直接做复杂度是 $O(n ^ 3 k ^ 3)$ 的，无法接受。你会发现这个转移是很多余的，考虑我们的操作形如若干个会产生贡献的点对 $(u_1, v_1), (u_2, v_2), \cdots$，满足 $u_i < v_i < u_{i + 1} < v_{i + 1} < \cdots$，每个 $[u_i + 1, v_i - 1]$ 有一些东西内部消化掉，是子问题不用管它；而 $[v_i + 1, u_{i + 1} - 1]$ 中间没有任何贡献，$[?, v_i]$ 任意向右扩展即得 $[?, r]$，其中 $r \in [v_i + 1, u_{i + 1} - 1]$。于是只要不产生贡献，区间拼接就是没有必要的，由中间向两边扩展亦可。

优化转移考虑分为产生贡献和不产生贡献的两部分，前者只需 $f_{l, r} \gets \max (f_{l + 1, r}, f_{l, r - 1})$ 即可；后者仍然需要枚举中点 $mid$，但此时我们要求 $a_l \equiv a_{mid} \pmod n$，这样的 $mid$ 数量不超过 $k$ 个，提前存下来枚举之即可。时间复杂度降到了 $O(n ^ 2 k ^ 3)$。

这样做常数非常小，180ms 跑得飞快。至于文章开头的画面，是因为我犯【数据删除】使用了常数极大的断环成链。

代码。