【题解】[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}\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'$，$B$ 后面接的是 $B'$，那么根据以上结论，$A',B'$ 中必定存在一个，使得其前缀最大值均为原序列前缀最大值。
令 $A'$ 的前缀最大值均为原序列前缀最大值，$B'$ 同理。设还没有填入的元素中，原序列的前缀最大值有 $x$ 个，设这 $x$ 个元素中有 $x-k$ 个进入 $A'$，$k$ 个进入 $B'$，$B'$ 中还有 $m$ 个不是原来的前缀最大值，却变成了 $B'$ 的前缀最大值。
那么需要满足：
$$ 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)$。