CF1768

vp。

A. Greatest Convex

。

B. Quick Sort

记 为序列 形如 的最长子序列长度，则答案为 。

C. Elemental Decompress

每个数在序列 中至多出现两次，否则必定无解。

考虑从大到小放入数 ，根据出现次数分类讨论。

• 出现 次：设 ，则必有 或 。无论哪种情况都会在 与 中各留下一个之后可以任意放的空位。
• 出现 次：设 ，则令 必定不劣。
• 出现 次：需要两个上文中提到的空位，若空位不足则无解。

D. Lucky Permutation

手玩一下可以发现，逆序对个数为 的排列一定形如 。

也即存在位置 ，满足

• 。
• 。

下文中称 为关键点。

---

前置结论：对于排列 ，设其置换环数量为 ，则通过交换操作使其变为升序的最小操作次数为 。

证明很简单。对于每大小为 的置换环，可以通过 次操作使其有序。

---

尝试对于 中的每一个 ，计算其作为关键点的最小操作次数。

根据 与 是否在同一个置换环中分类讨论。设原排列共有 个置换环。

• 在同一个置换环中。继续讨论。
  • 且 ：把剩下元素排序即可。答案为 。
  • 与 满足其一：一次操作，剩余元素置换环数量为 。答案为 。
  • 且 ：两次操作，剩余元素置换环数量为 。答案为 。
• 不在同一个置换环中：两次操作，原先所在的置换环合并，剩余元素置换环数量为 。答案为 。

综上，若存在 与 在同一个置换环上则答案为 ，否则为 。

E. Partial Sorting

操作次数显然不超过 。

记 为可以通过不超过 次操作变为有序的排列数量。则有

。只有初始有序的排列。

对于 ， 与 至少有一个区间已经归位，或者只有 无序。简单计算可得方案数为 。

对于 ，第一次操作必须使 与 中任何一个区间归位。也即 中所有数全部出现在 中 或 中所有数出现在 中。

容斥，枚举有 个 中的数出现在 可得

。

直接按柿子算即可。

F. Wonderful Jump

tourist 都没场切的神仙题。

暴力怎么做？设 表示到 位置的最小代价，枚举从哪个位置转移。 显然过不了。

发掘一下题目的性质。

结论 ：若一步从 跳到 最优，则有 。

反证法。若存在 且 ，则经过 中转的代价为 。由于 ，从 直接跳到 一定更劣。

结论 ：若一步从 跳到 最优，则 。

由于 ，一步一步挪过去的代价一定不超过 。由结论 ，一步跳过去的代价为 。于是有 ，化简一下就得到上面的式子。

下面证明利用上述结论转移的复杂度为 。

对于 ，步长不会超过 。

对于 ，这样的 只有不超过 个。若转移时钦定 严格小于 ，则对于相同的 总转移区间长度之和不会超过 。均摊单次 。