题解：CF2124I Lexicographic Partition

这个题太厉害了！

首先第一步你要观察，如何写 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$。分别考虑对应的情况：

什么时候会出事？连续两次都只能填最小的，也就是有一对父子同时有 $\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$，所以就矛盾了。

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

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