CF1710E Two Arrays

首先二分答案 $mid$，将 $a_i + b_j \le mid$ 的看成是 $0$，否则是 $1$。那么 A 想最后留在 $0$，B 最后留在 $1$。每一步肯定是在 $01$ 间交替，可以建一个二分图，将它复制 $1000$ 次，使得每条边 $(u,v)$ 在任意两个复制的图之间都出现。

则这个问题等价于一开始在一个 $1$ 的点，每次走到二分图的另一边，把上个点删掉，走不了的就输了。这是一个经典结论：

那么只需要求出这个二分图的最大匹配，删掉起始点再求一次看看是否相等即可，而复制了 $k$ 次的二分图 $G^k$ 的最大匹配 $|M^k|=k|M|$，证明如下：

所以只需求出原图最大匹配，可以将 $a,b$ 从大到小排序，$1$ 的点是左上角的一个凸的轮廓线。考虑 hall 定理，即求出 $\max\limits_S (|S| - |N(S)|)$。那么选出的 $S$ 中，一定不存在 $(i,t),(j,t)$ 使得 $i<j$ 且 $(i,t) \notin S, (j,t) \in S$，这是因为 $i$ 行的 $0$ 个数肯定小于等于 $j$ 行 $0$ 个数，换成它肯定不劣，列也同理。所以 $S$ 肯定是一个左上角的矩形（只有前缀的行列），那么枚举行数是 $i$，再双指针处理一下列 $j$，当且仅当 $j+1$ 列权值 $>0$ 才加入，做个前缀和优化一下即可线性求出。

对于删掉起始点 $(x,y)$ 的最大匹配也类似，不过要将 $(x,y)$ 移到行中 $1$、列中 $1$ 数量相同的行/列中最后一个就行。

复杂度 $\Theta(n\log V)$。