【题解】[AGC028E] High Elements

题目链接：[AGC028E] High Elements

题意：

你有一个 $1,2,\cdots ,n$ 的排列 $P$。设一个长度为 $n$ 的 $01$ 字符串 $S$ 合法，当且仅当，先设两个空序列 $A,B$，我们按照 $1$ 到 $n$ 的顺序，若 $S$ 当前位为 $1$ 则把当前位的 $P$ 添加到序列 $A$ 的末尾，否则添加到序列 $B$ 的末尾，使得 $A,B$ 的前缀最大值个数相等。求字典序最小的合法字符串 $S$。

$1\le n\le 2\times {10}^5$

$\text{orz i}\text{red}\text{odwad}$ /se

首先给出结论：

对于一组合法的 $A,B$，一定可以使得 $A,B$ 中的某一个序列的所有前缀最大值，都是原序列的前缀最大值。

证明的话，可以考虑每次分别从 $A,B$ 中选出一个，是当前序列前缀最大值，却不是原序列前缀最大值的位置，并把他们交换。

这样两边就恰好都少一个前缀最大值。因为，一个非前缀最大值的位置，在新序列中成为前缀最大值当且仅当：原序列中他前面比他大的元素都在另一个序列。

考虑一个贪心，每次尝试在当前位置放 $0$，即将当前元素放入 $A$ 序列，判断是否仍然存在合法解。若存在，则可以在当前位置放 $0$；否则就只能放 $1$ 了。

那么设填到某一个位置之后，序列 $A,B$ 的前缀最大值个数分别为 $c_a,c_b$，最大值分别为 ${\text{mx}}_a,{\text{mx}}_b$，我们现在希望判断当前局面下，是否存在一种方案使得往后填充能合法。

设接下来的元素往 $A$ 后面接的是序列 $A^{\prime }$，$B$ 后面接的是 $B^{\prime }$，那么根据以上结论，$A^{\prime },B^{\prime }$ 中必定存在一个，使得其前缀最大值均为原序列前缀最大值。

令 $A^{\prime }$ 的前缀最大值均为原序列前缀最大值，$B^{\prime }$ 同理。设还没有填入的元素中，原序列的前缀最大值有 $x$ 个，设这 $x$ 个元素中有 $x-k$ 个进入 $A^{\prime }$，$k$ 个进入 $B^{\prime }$，$B^{\prime }$ 中还有 $m$ 个不是原来的前缀最大值，却变成了 $B^{\prime }$ 的前缀最大值。

那么需要满足：

$$c_a+x-k=c_b+k+m$$

即

$$2k+m=c_a-c_b+x$$

观察发现在当前的情况下，$c_a,c_b,x$ 都是定值。因此我们只需要知道，是否存在一个 $2k+m$，能够拼出 $c_a-c_b+x$。

容易发现，若 $s$ 是可被拼出来且 $s\ge 2$，则 $s-2$ 也是可以拼出来的。因此我们只需要记录能够拼出的奇数 $max$ 和偶数 $max$ 即可。

对于 $2k+m$ 的处理，我们发现对于一个原序列前缀最大值，其系数为 $2$，非原序列最大值，系数为 $1$。则我们只需要给这些元素钦定这样的系数，然后拿权值线段树维护，序列第一个数为 $i$，所能拼出的最大的奇数、偶数。

时间复杂度 $\mathcal{O}(n\log n)$。