JOISC2017_J Abduction 2
由于权值较高的路不会被权值较低的路线影响，所以首先考虑将 \(h+w\) 条边按照权值降序排序，再考虑应该的最优决策方案。
注意到每一条路都横跨原始的矩形，这样以出发点为中心向上下左右发散就会有 4 条边构成一个小矩形。
考虑维护这个矩形每条边的最大路径数，这样就可以在新一条边加入的时候维护答案和被其切成的更小的矩形。
初始要枚举是东西走还是南北走。
时间复杂度 \(O((H+W)Q)\)
细节比较多，要充分考虑各种情况。
杂项题解
发布时间 2023-06-02 15:52:12作者: Optima_Xu