为了让复杂度能看一点，Dij默认使用Fib堆优化的Dij。
Range Query数据结构
包括线段树，k-dt和一些别的奇怪数据结构(比如分块?)。不再多说。
分块有一个应用挺好玩。
例题
CF786B Legacy
线段树优化建图板子题，不再赘述。
最小值最大，显然二分答案。
然后就变成，如果选了\(x\)，那么\([x-mid+1,x+mid-1]\)全都不能选。2-SAT。
爆力线段树连边，可以做到\(O(n\log n\log v)\)。这就很拖拉机。
发现每次连边长度全都是一样的，所以可以给数轴按这个长度分块，那么每一次连边恰好都是一个块的前缀和一个块的后缀，可以每块一个前后缀和解决。值域1e9?把没有东西的块和没有东西的位置都忽略就好了。单次复杂度就是线性。
滑动窗口
当我们要支持 点到区间连边 或者 区间到点连边，并且区间排序后左右端点均递增，形成一个滑动窗口，就可以考虑滑动窗口优化建图。
具体做法是，我们维护一个\(pos\)，把每个区间拆成从\(pos\)出发的一个前缀一个后缀。这样做的前提是\(pos\)在区间里，所以我们在扫的时候同时维护一个\(pos\)。
一开始初始化\(pos=r_1\)。如果\(l\)超过了\(pos\)，那么我们就更新\(pos\)为当前的\(r\)。你发现每一个点只会被连最多两次，一次\(pos\)在左边，一次在右边。所以它的复杂度确实是线性。
例题
又 见 面 了
你发现这个同时是一个定长的滑动窗口，这就很好，于是我们可以直接套用滑动窗口优化建图。
最短路算法本质优化
对于一类”单点到…连边”的问题有奇效，别的问题也不是不能考虑，当然如果是反过来的话可以考虑反图（
例题
请仔细看空间限制!128M不是可以随便开的。
发现是一个点向一个矩形连边，立刻有两种想法 : 树套树或者k-dt。
显然是树套树简单一些（bushi，所以我们先考虑树套树。
线段树套线段树，直接把矩形拆成\(\log^2 n\)个结点，然后进行连边，得到的新图点数是\(O(n\log^2 n)\)，边数\(O(m\log^2 n)\)，Dij的复杂度是\(O(n\log^2 n\log v+m\log^2 n)\)。时空双爆炸。
考虑到这\(n\log^2 n\)个点里面有很多是没用的。具体地，我们在内层树上只建立原图中点的线段树，空间复杂度就降为\(O(n\log n)\)。这样可以做到边数\(O(m\log^2 n)\)，Dij复杂度是\(O(n\log n\log v+m\log^2 n)\)。
这些边还是存不下!怎么办呢?
考虑我们并不加边，而是直接在树套树上进行增广。Dij的增广，在这题中就是一个矩形对一个值取\(\min\)，此外还要支持查询最小值，这可以很容易地用树套树维护一个取\(\min\)标记来实现。
k-dt做法是一样的，我们把点插入k-dt，并直接利用k-dt进行增广，每次松弛就是Range Query之后打上矩形对某个东西取\(\min\)的标记，要取出最近的点就维护一下子树\(\min\)，复杂度是时间\(O(n+m\sqrt{n})\)，空间\(O(n+m)\)。这个大概比树套树要好写很多?
代码这里有。写的当然是k-dt。在洛谷上明明是过了的（
最短路性质
基本理论
最短路有一个性质是说，两个点之间连很多条边等价于连最短的那条边，或者说最短路会自动给这些边取\(\min\)。
如果我们应该连边\(a\stackrel{w}{\longrightarrow}b\)，实际上只要保证有一条\(a\stackrel{w}{\longrightarrow}b\)，并且其它所有\(a\stackrel{w^\prime}{\longrightarrow}b\)都满足\(w^\prime\geq w\)即可。
当然最长路是对称的。差分约束就是最短路。
所以当看到一些奇怪的边权的时候，可以尝试把它们化成\(\min\)的形式，然后就可以直接拆开\(\min\)了。
例题
我们从一道经典题谈起。
看到这个题，首先我们有一个显然的结论，那就是lcp就是lca深度(根深度为0)。
考虑对每条边做一个拆点，我们把一条边权为$w$的边$i$中间加上一个入点一个出点，记为$in_i,out_i$，并连边$in_i\stackrel{w}{\longrightarrow}out_i$。
然后考虑原图中的点仅仅表示边的连通性，所以一个暴力的想法就是去掉原图中的点，而对每个点把它周围所有的边都连一连。具体地，对于每条连向点$u$的边，把它的出点向每条从$u$发出的边的入点连边，边权是lca深度。
如果遇到一个点周围有很多边，我们得到的边数就是$O(n^2)$，会爆炸。
因为最短路是对重边取$\min$，我们可以考虑能不能把lca深度也搞成一个$\min$的形式(核心思想)，这样就可以利用最短路的取$\min$来处理lca深度了。
容易想到使用dfs序lca。dfs序lca的结论是，如果我们记录一棵树的欧拉序(每经过一次都记录一次)，那么两个点的lca就是它们第一次被访问的位置之间深度最小的点。
所以如果我们设$d_i$表示dfn中第$i$个位置上那个点的深度，$id_u$表示点$u$第一次被访问的时间，那么就有
\[\mathrm{dep}(\mathrm{lca}(u,v))=\min_{i=id_u}^{id_v}d_i\]然后呢?考虑一个$d_i$什么时候会参与这个取$\min$的过程，应该是查询的两个点，一个点在它前面，一个点在它后面的时候。
换句话说，这个点的贡献就相当于给它对应的前缀连到后缀，后缀连到前缀，边权是它的深度。!!!我们已经得到做法了!
这里可以使用线段树优化建图，不过更好的方法是使用前后缀和优化建图。
前后缀和优化建图是什么?以前缀和为例，我们新建一排点表示前缀和，前缀和那一排中的点$i$连向点$i-1$和原序列中的第$i$个点，这样它实际上连到了原序列中的前$i$个点。我们可以使用这个结构支持一个点向一个前缀连边。前缀向点连边，点向后缀连边，后缀向点连边是同样的。
对于这个题，我们需要建四排点，分别表示前缀入点，前缀出点，后缀入点，后缀出点。
这里需要建立虚树，在虚树上求欧拉序，这一步没有难写到一定程度，但是实际上还可以简化，具体可以见别的题解。反正我没想着简化（
复杂度是$O((n+m)\log n)$。
这题还有一些别的做法，网上说的带$\log$甚至$\log^2$的树剖和树上倍增做法实在是没想明白，希望神仙们可以教教我/se
温馨提示 : 多测不清空，爆零两行泪!
代码这里有。不过确实很难写!需要一定的封装技巧才能让代码可读，这里我考虑了好久……
jzoj4858 Walk
jzoj的vip题……不管了，反正搜了个题号就写上来了。
题意大概是，有一张有向图，点有一个二进制的权值\(val_u\)，边没有边权，给了\(m\)条边，然后如果点\(u\)的权值是点\(v\)权值的子集，会连一条\(u\longrightarrow v\)。求1出发的单源最短路。
\(n\leq 2\times 10^5,m\leq 3\times 10^5,val_i\leq 2^20\)。
第一个结论是传递性，也就是如果额外连了\(u\longrightarrow v,v\longrightarrow w\)，那么一定也有\(u\longrightarrow w\)。
发现暴力连边的问题是，可能有很多点的点权是一样的，比如有\(\frac{1}{2}n\)个点点权是\(1\)，另外的点权是\(0\)，就会连出\(\frac{1}{4}n^2\)条边。
又发现点权很小，考虑对点权建一张边权全是0的图，把原图中的边表示为这个图中的路径，那么根据传递性我们可以类似FWT搞出\(O(v\log v)\)条边。
原图中每个点向它的点权连边，边权为1，表示要走一步需要付出的代价；点权向原图中的点连边，边权为0；原图中的边直接连。
使用01bfs，我们就在\(O(n+m+v\log v)\)的复杂度内解决了这个问题。