比赛：USACO 2024 JAN G

首先发现一个显然但重要的性质，

考虑把题目中的直线互相划分，形成一个网格图，然后我们以每个格子的边为单位，进行移动，

发现从一个格点开始走，当且仅当走过一段奇数长度的段，下一步会变向。

也就是说移动的过程相当于，从一个格点开始，不断地跳到下一个奇数段的末尾。当然，忽略一开始走到的格点之前的路径，和，最后走到的格点之后的路径，因为这些边界部分是可以快速计算的。

一般这类优化暴力移动的问题，我们可以考虑倍增。

设 $f(i,j)$ 表示从第 $i$ 个横坐标开始，向东走的第 $2^j$ 个奇数段。$g(i,j)$ 表示从第 $i$ 个纵坐标开始，向北走的第 $2^j$ 个奇数段。

由于起点可能不在格点上，先把它走到第一个格点。然后由于走的时候一定是 "向东 向北 向东 向北 ..." 交替着走的，于是 $f$ 和 $g$ 一起跳即可。最后再计算剩余走的情况，要么是 "向东 + 向北一点"，要么是 "向北 + 向东一点"，可以 $O(1)$ 计算。

时空复杂度 $O(n\log n)$。