Link

题解

发现询问次数很少，可以支持单次询问 \(O(N+M)\) 的做法，这样就可以枚举每条道路然后去做。

但直接做貌似不太行，所以先发掘一些性质。

假如询问点 \((X,Y)\) 处在全局流量最大的道路上且方向与道路走向一致，那么答案能轻松得出。

否则这条道路会将整张图分成两个区域（不含流量最大的道路），显然不能从一个区域到达另一个区域。

这样我们就可以以询问点所在的区域（或者处于流量最大的道路内但方向指向了所在的区域）递归下去，最多递归 \(O(N+M)\) 次。

对于局部图，我们还是选择当前流量最大的道路，但道路上的点的答案就不是那么显而易见，但也是好做的，设道路的两端的坐标为 \(l,r\)，那么两端都会与之前的某两条道路相交，答案是好算的，设它们的答案分别是 \(ansl,ansr\)，那么当前道路坐标为 \(x\) 的答案就是 \(\max(ansl+x-l,ansr+r-x)\)。

对于特殊情况：在当前流量最大的道路但方向不对，其实做法是一样的，继续递归下去即可，但初始递归的时候我们横向和纵向都要递归一遍。

快速找到横向/纵向区间内流量最大的道路显然用 ST表 维护。

时间复杂度：\(O(Q(N+M))\)

AC Code

https://atcoder.jp/contests/joisc2017/submissions/37699257