题解：CF2124I Lexicographic Partition

strapplE · 2025-09-07 16:47:30 · 题解

这个题太厉害了！

首先第一步你要观察，如何写 spj，也就是根据已知排列求每个前缀的答案。先考虑整个排列 p_1,p_2,\dots,p_n 的答案。

对于字典序最优这种问题，别无它法，必然是贪心。第一个数肯定是 p_1，下面想第二个。设最靠前的 <p_1 的位置为 p_a，则如果 a=2，直接归约到 [2,n] 的答案；否则考虑 p_{1\sim a} 最大的为 p_b，将会归约到 [b,n] 的答案。

这样就可以 O(n^2) 的算整个排列的答案了。但这还远远不够，想要优化，我们必须要换一种思路，从每次往后加一个数的角度入手。

这里我们不加证明的给出（其实直接理解即可），我们可以直接维护一个栈，表示目前的答案。每次加一个数时，就会弹一个后缀，把“在它之前第一个比它大的数到它的区间最小值之后的数”删掉。这样我们就可以很轻松的维护数据结构做到 O(n\log n) check 了。

回到正向构造部分。

注意到栈的结构十分特殊，因为每个时刻栈的大小都确定了，就为 x_i，因此弹出多少个元素也是固定的。这就说明，栈里面的所有元素的坐标都是已知的（换句话说，我们知道任意时刻栈都由 p_{z_1},p_{z_2},\dots,p_{z_{x_i}} 构成，z_j 是确定的）。

根据这个结构，考虑加完 p_i 后得到的栈 S_i，设倒数第二个元素为 p_j（一定存在，因为 p_1 永远在栈中）。则 S_i 就是 S_j 填加 p_i 的结果。

这启发我们，将 j 向 i 连一条边，形成一棵树，S_i 就是根结点 1 往 i 的路径顺次排列的结果。

因为一个 p_i 出现的时间是连续的（被删之后就再也不会复活了），因此它的子树对应的位置也是连续区间，也等价于这棵树的 dfn 序就是 1\sim n。因此 i 如果不是叶节点，则 i+1 一定是 i 最靠左的儿子。

考虑按一种方式来确定答案。因为点之间的顺序很明确，所以直接 dfs 确定。

可以定义 solve(x,l,r) 表示将确定 x 的子树，填数范围在 [l,r] 中。根据直觉，我们要么填最小的数 l，要么填最大的数 r。分别考虑对应的情况：

• 填最小的：儿子之间肯定是从左往右地递增去填（否则到第二个儿子的时候前面删不掉），因此划分区间的方案是固定的。只要前面 <x 的部分不捣乱即可。

• 填最大的：为了防止前面捣乱，相当于加了一个隔离挡板，后面的人删不到前面去，但是如果有多个儿子，就会出现删不掉的点，所以此时 x 只能有一个儿子。

什么时候会出事？连续两次都只能填最小的，也就是有一对父子同时有 \geq 2 个儿子。这里给一个充要的证明：

引理：x 如果有不少于两个儿子，则对于其任意两个儿子，设左边的为 y，右边的为 z，则 p_x<p_y<p_z。

证明是容易的，就根据我们之前那个模拟栈的思路，到 z 的时候 p_x 会作为最小值把后面的弹掉，而这些数都不能超过 p_z，于是就对了。

而如果存在 y 是 x 的儿子，z 是 y 的儿子，且有 p_x<p_y<p_z，那从优化的角度上，没道理不删 p_y，所以就矛盾了。

此时把这种情况排掉之后，就可以直接递归下去构造了，时间复杂度线性。

代码稍微有点写丑了，当时理解还不够深刻。大概思路和本文是相符的，凑合看看吧。