前面部分参考了yyb的题解。
题意简述
给你一个 $1$ 到 $n$ 的排列 $P$ 。你需要求出一个长为 $n$ 的 01 字符串 $S$ 。构造两个序列 $X, Y$ ，按标号升序考虑每个 $P_i$ ，如果 $S_i = 0$ ，则加入 $X$ 末尾，否则加入 $Y$ 末尾。若 $X$ 与 $Y$ 的 前缀最大值个数相等，则称 $S$ 是好的。
求字典序最小的好的 $S$ 。$1\le n\le 2\times 10^5$ 。
主要思路
显然，可以逐位确定，只需判断给定一个 $S$ 的前缀后，合法解的存在性。
先来证明一个结论：只要合法解存在，则总有一个好的 $S$ 使得 $X, Y$ 中，至多只有一个中有前缀最大值不为 $P$ 的前缀最大值。
如果 $X$ 中存在「原本不是 $P$ 中前缀最大值，但是现在数列的前缀最大值」的数，那么对于这个数， $P$ 中在它前面的最大值被分配到了 $Y$ 中。假如对于 $Y$ 也有这样的位置，将这两个位置所在的序列调换，则交换之后两个序列的前缀最大值的个数都会减少 $1$ 。所以，经过若干次交换之后，必定能够使之多只有一个序列中有前缀最大值不为 $P$ 中前缀最大值。
不妨设 $X$ 中所有前缀最大值均为 $P$ 的前缀最大值。假设前 $i-1$ 位已经构造完毕，现在考虑第 $i$ 个元素可以放在哪个序列。设目前 $X, Y$ 中的最大值分别为 $M_X, M_Y$ ，前缀最大值个数分别为 $C_X, C_Y$ 。
设 $P$ 中标号 $[i, n]$ 的前缀最大值个数为 $Q$ ，而 $Y$ 在接下来的数列中会有 $k$ 个前缀最大值为 $P$ 的前缀最大值，则 $X$ 中会有 $Q - k$ 个。再设 $Y$ 中非 $P$ 的前缀最大值的前缀最大值的个数为 $m$ 。由于 $X, Y$ 中前缀最大值的个数相等，有以下条件：
$$C_X + (Q - k) = C_Y + k + m$$
化简后得到：
$$2k + m = C_X + Q - C_Y$$
其中右边是已知的常量。
由于在 $k > 0$ 或 $m > 1$ 时， $2k + m$ 可以减少 $2$ ，因此若有一个方案能够满足 $2k + m \ge C_X + Q - C_Y$ 且 $2k + m \equiv C_X + Q - C_Y \pmod{\! 2}$ ，就必然存在满足 $2k + m = C_X + Q - C_Y$ 的方案。
实现时，先对 $P$ 倒序做带权的最长下降子序列，其中 $P$ 中的前缀最大值权为 $2$ ，其余元素权为 $1$ ，分别维护为奇数和偶数的最大长度。这一步可以线段树实现。正在确定 $S$ 的第 $i$ 位时，只需要查询从标号 $j$ （$j\ge i, P_j > M_Y$）的元素开始，长度与当前的 $(C_X + Q - C_Y)\bmod 2$ 同余的最长上升子序列的最大长度即可。
复杂度 $O(n\log n)$ 。
参考代码
咕咕咕