AGC028E High Elements

题意：给出一个长度为 的排列 。

称一个长度为 的 字符串 合法，当且仅当：

初始时有两个空序列 ，按 的顺序，若 则把 添加到序列 末尾，否则添加到序列 末尾。最终 的前缀最大值个数相等。

求字典序最小的合法字符串 。

，时限 。

---

考虑经典的按位贪心：从前往后处理，每次判定填 后是否有解，能填 则填 。

问题转化为对 逐位确定，并判定是否有解。

记 为序列 的前缀最大值集合。

不难发现，对于 ， 在分到 中之后也必然成为前缀最大值。

• 性质：对于一个确定的前缀 ，若存在合法的补完方案，则一定有一种方案满足 或者 。

  其中 指 新增的前缀最大值。

• 证明：

  若存在 ，满足 ，考虑将两者交换，注意到使得 在 中不为前缀最大值的元素一定存在于 （另一个序列）中，所以交换后两者都不再是前缀最大值。

  的前缀最大值个数同时减一，仍然满足条件。可以不断进行该类交换，即可得到满足性质的解。

（这里利用了判定子问题的特性，按需推理。若直接考虑刻画答案的性质，则较为吃力）

现在我们已经填写了 ，需要判定否可行。

分别考虑 或者 ，下文只介绍 的情况。

记目前 中的最大值分别为 ，前缀最大值个数分别为 ， 。

设 ，其中 为非 中的元素个数， 为 中的元素个数。

则有：

此时左侧 是个常数，只需判定是否存在一种 使得 满足条件。

即：令 中元素权值为 ，其余元素权值为 ，判定 中能否选出上升子序列使得权值和为给定值，且首元素 。

不难发现，若能得到权值和为 的上升子序列，那么通过除去最小权值一定能得到权值和为 的，故只需记录奇偶最大值。

考虑 DP，记 表示后缀 中和为 奇/偶 的最大值，且必选 ，此时 恰为上升子序列中最小值。

转移如下：

容易线段树优化。

在判定时，需要查询后缀 中值 ，奇偶性为 的上升子序列的最大权值。即

这个也可以线段树优化。

复杂度 。