CVBB ACM Team

toby:

这是一个经典的数学问题（许多书上有提到）。当然不知道结论也可以猜。下面给出一个证明：

首先可以发现 (n, m) 格肯定是最后拿到的，拿到的人就输了。 当 n==1 && m==1 时，由于只有一个拿取的方案，所以先手必败。 其他情况，假设先手必败，则先手取 (1, 1)，后手必有必胜方案，不妨设为取 (a, b)，那么先手只需要在第一手取 (a, b) 就可以得到一致的必胜局面，导出矛盾。故先手必胜。

Dirty: 无。考场花了 5 min 重导这个结论。

yuki:

考虑到如果交换了 $b_x$ 和 $b_y$（交换 $a$ 是等价的），答案将从 $|a_x - b_x| + |a_y - b_y|$ 变为 $|a_x - b_y| + |a_y - b_x|$ 那么 $a_x$ 和 $b_x$ 的大小关系和 $a_y$ 和 $b_y$ 的大小关系一定是相反的，否则交换后的结果要么不变，要么变大。因此把输入分为两类 $a \leq b$ 的和 $a > b$ 的。

假设：$a_x \geq b_x$ 那么可能交换的 $a_y < b_y$，按 $b_y$ 从小到大遍历所有的第二类元组，不断把第一类元组加入线段树，保持线段树中 $a_x \leq b_y$，再以 $a_y$ 作为分界在线段树上分别查询 $b_x < a_y$和 $b_x \geq a_y$ 两种情况的最优解。

Dirty： 线段树写错了（我是笨蛋）

yuki:

exgcd解方程，再凑一凑答案。

Dirty： 考虑了最后一杯水可以不倒掉的情况，但只考虑了一半（我是笨蛋）