优化建图
分层图
例1 [P4568] 飞行路线
分层图模板题
给定一张图，你有k次机会将一条边修改权值为0，问最短路
k较小时，可以用分层图解决
例2 [P1266] 速度限制
注意到n，v比较小，考虑分成v层图，但是时间空间会炸
发现每一层对于边u->v的转移相同，考虑只分节点，共用边，即开dis数组开第二维度存v，将dis[x][v],x,v打包放入堆中维护
得出结论：
分层图中如果每层的边转移相同，可以只存点，用二维dis数组维护
曼哈顿距离 & 切比雪夫距离
对于两点：\((x_1,y_1),(x_2,y_2)\)
曼哈顿距离：\(d=|x_1-x_2|+|y_1-y_2|\)
切比雪夫距离：\(d=max(|x_1-x_2|,|y_1-y_2|)\)
转化
一个点 \((x,y)\) 的坐标变为 \((x+y,x-y)\) 后，原坐标系中曼哈顿距离 = 新坐标系中切比雪夫距离。
一个点 \((x,y)\) 的坐标变为 \((\frac{x+y}{2},\frac{x-y}{2})\) 后，原坐标系中的切比雪夫距离 = 新坐标系中的曼哈顿距离。
证明略
记忆技巧：曼哈顿比切比雪夫名字短，所以转化要除以2，正数更受欢迎，所以先加再减
适用情景
有曼哈顿距离或切比雪夫距离（废话
对这个距离做性质相异的操作（如对曼哈顿取max）
P7561 [JOISC 2021 Day2] 道路の建設案 (Road Construction)
先转换模型：曼哈顿\(\to\)切比雪夫
二分第\(k\)便宜的点对，问题变成二维数点，扫描线+树状数组解决
接下来就是统计答案了，搞了个很弱的做法（类似平面最近点对），差点跑满10s（如何优化）
P6751 [IOI2019] 视觉程序
（题解大佬用二进制加法器实现了，%%%
看到题目中曼哈顿距离，考虑转成切比雪夫，即求新图中\(max(x_1-x_2,y_1-y_2)\)恰好等于\(k\)
两维分开考虑，容斥分为\(\le k\)和\(\le k-1\)，对于单个贡献，向后或上\(k\)位就懂得有没有了
注意会出现，对于一个维度，两个点重合于一个位置的情况
数据结构优化建图
线段树
主席树
树套树
P5471 [NOI2019] 弹跳
直接树套树建边，空间复杂度是\(O(n\log^2n)\)的，过不了
考虑在\(dijkstra\)时，每次从堆中取出时间最小的一个矩形，此时该矩形内的点一定只能被该矩形松弛，更新这些点，并从树套树上删掉，然后把出边丢进堆里继续做即可
与常规\(dijkstra\)不同的是，这里堆里不存点，存边（矩形），因为存点的话，还得枚举出边，反复更新一些点的值，这显然不够好，而一个矩形内的点的状态都是一样的，缩起来更新即可
至于为什么平常dijkstra不用存边的方法，呃，其实和存点效果一样，这里是多个点连同样的边才有这种优秀性质的