ARC114F Permutation Division

题意 ： 给出排列 。

Alice 需要将 划分为恰好 个连续区间，然后 Bob 将它们重新排列并拼接，得到排列 。

Alice 时希望 的字典序最小，B 希望 的字典序最大，求最终得到的 。

，时限 。

---

Bob 的策略显然是按照每一段的第一个数从大到小排序。

注意到 一定是一段的开头，分类讨论。

此时 A 分段的开头一定是 ，这可以使得 ,其他方法都会使得 。

此时其他段的首位都必须 ，这样才能使得 ，显然这是下界。

显然 的字典序要大于 ，我们可以先考虑最大化 的最长公共前缀长度。

二分这个长度 ，考虑如何判定。

可以在 内切分出 段，满足开头是下降子序列（这样就会保持原序），记最后一段的开头是 ，则需在 后面切分出 段，要满足每段开头均 。

记 表示以 结尾（以 开头）的最长下降子序列，枚举 判，数 后面 的元素个数，看看是否 即可判定。

得到 之后，需要最小化之后的排列。

继续考虑上述策略，对于（合法的） ，我们在 后面的决策显然是找最小的 个元素作为开头，其中第 小的就是下一位。

最小化 的值之后，策略已经确定。

复杂度 。

• 总结：在字典序问题中，对方案的一部分进行最大化，即可确定（强力约束）决策。