CVBB ACM Team

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： 考虑了最后一杯水可以不倒掉的情况，但只考虑了一半（我是笨蛋）