其实今天也不是第一次接触这个东西吧，只不过感觉这东西套路性蛮强的就单独将它们拎出来整了个 blog（
在图论问题中，有时暴力建边复杂度过高，无法通过，但建出的边有一些比较好的性质（比如都是某个区间中的点向另一个区间中的点连边），此时就可以考虑数据结构优化建边降低复杂度。
线段树优化建图
u1s1 这个大概是最基础的优化建图的方式了吧（
线段树优化建图可用于优化以下形式的建图方式：
- 对于区间 \([l_1,r_1]\) 中的所有点，向 \([l_2,r_2]\) 中所有点连边。
暴力 \(\mathcal O(n^2)\) 建边显然 TL ML 双开花，不过注意到这里有我们熟悉的”区间“二字，因此我们考虑使用擅长处理区间的线段树来处理这个问题，我们建两棵线段树，一个叫”入线段树“，一个叫”出线段树“，入线段树的每个节点 \([l,r]\) 向它的两个儿子 \([l,mid],[mid+1,r]\) 连边，叶子节点 \([x,x]\) 向对应的点 \(x\) 连边；出线段树也同理，每个节点 \([l,r]\) 都有从它的两个儿子 \([l,mid],[mid+1,r]\) 连出去的连边，每个点 \(x\) 向对应的叶子节点 \([x,x]\) 连边，那么上述建边操作可这样优化：
- 建立一个虚点 \(P\)
- 将 \(l_1,r_1\) 拆分成 \(\mathcal O(\log n)\) 个子区间并从出线段树上这些区间对应的节点向点 \(P\) 连边
- 将 \(l_2,r_2\) 拆分成 \(\mathcal O(\log n)\) 个子区间并从点 \(P\) 向入线段树上这些区间对应的节点连边
然后按照题目要求跑最短路/SCC 缩点/拓扑排序/...... 即可。
不难发现这样与暴力建边是等价的，复杂度则由 \(n^2m\) 降到了 \((n+m)\log n\)。
主席树优化建图
其实和线段树差不多吧，只不过把线段树换成了主席树（大雾，等于啥也没说
具体来说，主席树优化建图适用于以下形式的建图方式：
- 从点 \(x\) 连向区间 \([l,r]\) 中满足 \(a_y\le a_x\) 的点 \(y\) 建边
如果是求 \([l,r]\) 中满足 \(a_y\le a_x\) 的 \(y\) 的个数，倒可以主席树做，但这里要从 \(x\) 向这些 \(y\) 们建边，所以这时候咱就要用到主席树优化建图了。
具体来说我们将 \(a_i\) 离散化并对 \(a_i\) 建立主席树，主席树的某个版本 \(x\) 保存 \(a_i\le x\) 的点组成的线段树，当我们从点 \(x\) 连向区间 \([l,r]\) 中满足 \(a_y\le a_x\) 的点 \(y\) 建边时，只需在主席树上找到 \(a_x\) 对应的版本，并从 \(x\) 向这个版本的线段树上 \([l,r]\) 对应的区间连边即可。
点数 \(n\log n\)，边数 \(m\log n\)。
值得注意的一点是，由于建边的贡献不支持相减，因此形如”从点 \(x\) 向 \([l,r]\) 中满足 \(a_y\in[a,b]\) 的点 \(y\) 建边“这样的建图方式不能使用主席树优化，而要使用树套树优化，点数 \(n\log^2n\)，边数 \(m\log^2n\)
CDQ 分治优化建图
CDQ 分治优化建图适用于以下形式的建图方式：
- 从点 \(x\) 向满足 \(y<x,a_y\le a_x\) 的点 \(y\) 建边
一眼二维偏序，因此考虑使用擅长处理偏序问题的 CDQ 分治优化建图，具体来说，咱们分治处理 \([l,r]\) 时候统一从 \([l,mid]\) 中的点向 \([mid+1,r]\) 中满足要求的点连边。我们记 \(a_l,a_{l+1},\cdots,a_r\) 中出现过的值组成的集合为 \(S\)，那么我们将 \(S\) 中的值从小到大排序并各建立一个虚点，假设 \(S\) 中的值从小到大到大排序建立的虚点依次是 \(b_1,b_2,\cdots,b_m\)，那么我们连边 \(b_i\to b_{i-1}(i\in[2,m])\)，同时对于 \(i\in[l,mid]\)，在建立的一排虚点中找到 \(a_i\) 对应的点 \(b_j\) 并连边 \(b_j\to i\)，\(i\in[mid+1,r]\) 的情况也同理，只不过边的方向要反过来，即从 \(i\) 连向 \(b_j\)。显然这样我们即可实现从 \([l,mid]\) 向 \([mid+1,r]\) 中的点连边。如此递归下去即可完成建图。
点数 \(n\log n\)，边数 \(n\log n\)。
前后缀优化建图
前后缀优化建图适用于以下形式的建图方式：
- 从某段前缀 \([1,y]\) 向 \(x\) 的点连边
- 从点 \(x\) 向某段后缀 \([y,n]\) 中的点连边
- 从某段前缀 \([1,x]\) 向某段后缀 \([y,n]\) 连边
首先线段树优化建图肯定是可以搞定的，不过注意到这里的区间都是一个个前后缀，因此考虑使用更优秀的前后缀优化建图。我们建立 \(n\) 个虚点 \(s_1,s_2,\cdots,s_n\)，每个 \(s_i\) 保存着前缀 \([1,i]\) 中的点连来的边，以及另外 \(n\) 个虚点 \(p_1,p_2,\cdots,p_n\)，\(p_i\) 连向 \([i,n]\) 中的点。我们连边 \(s_i\to s_{i+1}(i\in[2,n]),i\to s_i\)，以及边 \(p_i\to p_{i+1}(i\in[2,n]),p_i\to i\)。这样一来这些操作就变得容易多了，对于操作 \(1\) 连边 \(s_y\to x\)，对于操作 \(2\) 连边 \(x\to p_y\)，对于操作 \(3\) 连边 \(p_x\to s_y\)。
点数 \(\mathcal O(n)\)，边数 \(\mathcal O(n+m)\)，dd 线段树优化建图 by 1log。