将题意转化为求白色点字典序最小最大匹配（黑点是原来点，白点是加入点），称之为最优匹配。显而易见，前缀答案大小不可能比最优匹配大（否则替换）。

接下来给出一种通用做法：如果对于一张二分图，可以花一定代价求出任意一组最小割，那么可以以多一个 $\log n$ 的代价求出最优匹配。

在此之前对最小割做定义：我们求出任意一组最大匹配，然后从左部，非匹配点出发。将可以到达的点全部加入队列，然后遍历。最后访问过的点称为左集，没访问过的称为右集。而两者在左部和右部的点集，将标注下角标。

设计 $F(S_1,S_2,S_3)$ 表示 $S_2< S_1$ 且左部为 $S_2\cup S_1$，右部为 $S_3$，并且 $S_2$ 一定在最优匹配中。答案就是 $F(L,\varnothing, R)$ 。此时将 $S_1$ 分成 $X,Y$ 两部分且 $X< Y$，我们求出 $(S_2\cup X,S_3)$ 的最小割，记为 $(A_l,A_r),(B_l,B_r)$ 。注意到以下事实：

• $(B_l\cup Y,B_r)$ 的最优匹配一定包含 $B_l$：因为 $(B_l,B_r)$ 的最优匹配已经包含 $B_l$，考虑匈牙利增广即可。
• $(S_2\cup X,S_3)$ 的最优匹配由 $(A_l,A_r)$ 和 $(B_l,B_r)$ 的最优匹配构成：因为 $A_l,B_r$ 之间没有边，而 $B_l,A_r$ 之间的边一定会让最短路变小（$B_l,A_r$ 都全在最大匹配中）。所以剩下的边都不是匹配边。
• $(S_1\cup S_2,S_3)$ 的最优匹配由 $(A_l,A_r)$ 和 $(B_l\cup Y,B_r)$ 的最优匹配构成：考虑从 $(S_2\cup X,S_3)$ 增广，因为 $A_r$ 已经全都在最大匹配，所以增广路不可能进入 $A$ 。

于是，$F(S_1,S_2,S_3)$ 由 $F(A_l\cup S_1,A_l\cup S_2,A_r)$ 和 $F(Y,B_l,B_r)$ 构成。容易发现一个点恰好递归到一侧，且 $S_1$ 大小减半，因此递归树深度 $O(\log n)$ 。

求最小割是容易解决的：从右到左贪心地找一组最大匹配。然后从每个非匹配白点出发，尝试访问剩下的点。这个可以通过对点建线段树，快速处理。