Bipartite Array 题解

思路

固定一个带符号数组 $a$。把逆序图的顶点二染色，等价于把数组位置分到两个颜色中，并且同色位置之间没有逆序。也就是说：

逆序图是二分图，当且仅当整个数组可以按原顺序划分成两个严格递增子序列。

于是原题变成：为每个 $p_i$ 选择正号或负号，并把所得数放入两条递增链之一。

子任务一：枚举全部符号

当 $n\le10$ 时，枚举 $2^n$ 种正负号。对每种数组显式建立所有逆序边，再用 BFS 二染色检查逆序图是否为二分图。找到第一组合法符号即可。

子任务二：维护两条链末尾的 Pareto 前沿

处理完前缀后，用 $(x,y)$ 表示两条递增链当前的末尾值。对新的 $p_i$，枚举正负号得到 $v$：若 $v>x$，可以把它接到第一条链；若 $v>y$，可以接到第二条链。

如果状态 $(x_1,y_1)$ 满足 $x_1\le x_2$ 且 $y_1\le y_2$，那么前者更容易接入后续元素，后者可以删除。每层转移后排序并保留 Pareto 前沿，同时记录父状态即可恢复答案。

子任务三：利用两条链的对称性压缩

进一步观察：处理到位置 $i$ 后，至少一条链的末尾一定是当前带符号值 $s_i$。两条链没有名字，因此只需记录：

• 当前 $p_i$ 选用的符号；
• 另一条链末尾能够达到的最小值。

设当前两条末尾排序后为 $x\ge y$，下一项的某个符号值为 $z$：

• 若 $z>x$，它可接到较大末尾之后，新状态的另一末尾为 $y$；
• 否则若 $z>y$，它可接到较小末尾之后，新状态的另一末尾为 $x$；
• 否则该转移不合法。

对下一项的正负两种符号分别取最小的“另一末尾”。每个位置只有两个状态，父指针恢复符号，时间和空间均为线性。

做法

1. 令正号、负号两个状态的“另一链末尾”初值均为负无穷。
2. 从左到右处理相邻位置。
3. 对当前两个可达符号状态和下一项两种符号，按上面的两链接入规则转移。
4. 同一下一符号只保留另一末尾更小的状态，并记录来自哪个当前符号。
5. 若最后两个状态都不可达，输出 NO；否则沿父指针恢复符号并输出 YES 与数组。

正确性证明：

• 任意二分染色的每个颜色类都不含逆序，所以对应一条严格递增子序列；反之，两条递增子序列内没有逆序边，把它们作为两个颜色即可得到二分染色。
• 每一步只需要把新值接到两条链之一，上述两个不等式完整枚举了全部合法接法。
• 对同一当前符号，另一链末尾越小越优；它能完成较大末尾状态可以完成的所有后续转移，因此只保留最小值不损失解。
• 归纳所有前缀，动态规划恰好保留存在合法两链划分的符号选择。最终可达当且仅当存在题目要求的带符号数组。

复杂度

对单个测试用例：

• 子任务一时间复杂度为 $O(2^n n^2)$，空间复杂度为 $O(n^2)$；
• 子任务二最坏时间复杂度为 $O(n^2\log n)$，空间复杂度为 $O(n^2)$；
• 完整算法时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

所有测试用例的复杂度按 $\sum n$ 求和。