\(\Theta(n^2)\) 建图是不合法的时候就要用一些优化建图的手段
线段树优化建图
在有些数据范围内是不允许我们把图上的所有边建出来的
那么以编号为下标建线段树，线段树上的每个节点的 \(l\) 和 \(r\) 就是把 \(l\rightarrow r\) 中的所有点缩到一个点表示
把每个原图节点拆成一个入点，一个出点，分别用两个线段树维护
我们在入点从上往下建边权为 \(0\) 的边，表示到了表示区间的点肯定可以到子区间；出点从下往上建 \(0\) 边，含义类似
入点线段树的每个点向出点线段树的对应位置的点建 \(0\) 边 ，从这里进必然可以出
区间连边就建立一个虚拟点，把出区间拆成 \(\log\) 份，连向虚拟点，边权为为 \(0/w\) 即可
后续进行最短路/网络流/2-sat就依题而定了
大概代码如下，听说被喷描述和代码不符了但是我也不知道咋改
Code Display
int ls[N<<2],rs[N<<2],rt1,rt2,tot,L,R;
inline void build1(int &p,int l,int r){
if(l==r){p=l; return ;} p=++tot; int mid=(l+r)>>1;
build1(ls[p],l,mid); build1(rs[p],mid+1,r); add(p,ls[p],0); add(p,rs[p],0);
return ;
}
inline void build2(int &p,int l,int r){
if(l==r){p=l; return ;} p=++tot; int mid=(l+r)>>1;
build2(ls[p],l,mid); build2(rs[p],mid+1,r); add(ls[p],p,0); add(rs[p],p,0);
return ;
}
inline void update(int p,int l,int r,int u,int w,int type){
if(L<=l&&r<=R){
type==2? add(u,p,w):add(p,u,w);
return ;
}int mid=(l+r)>>1;
if(L<=mid) update(ls[p],l,mid,u,w,type);
if(R>mid) update(rs[p],mid+1,r,u,w,type);
return ;
}
[SNOI2017]炸弹
首先可以处理出来每个点的控制范围，然后我们连边（点向区间）
注意这里是有向边，所以是父亲到儿子连
然后我们发现可以 \(tarjan\) 出来强连通的炸弹
依题意：我们缩点跑完之后接着 \(dfs\)，求出来每个炸弹爆炸后影响的最左端和最右端的点
最后求答案即可
前后缀优化建图
处理完全图连边的有效工具，模板题是 Codeforces587D
题目中涉及的建图是完全图连边，没连的边只有自己向自己，那么对于每个 \(1\sim n\) 的前缀建立虚点 \(s_i\)，拆开的另一个点的后缀点是 \(s'_i\)
那么题目中剩下的连边可以表示为
\(1.i\to s_i,s'_i\to i'\)
\(2.s_i\to s_{i+1},s’_i)\to s'_{i-1}\)
\(3.s_i \to (i+1)',i\to s'_{i+1}\)
这是对于选出来的边是匹配的限制的建边方式，每种颜色剩下的是一个匹配的方案就是把这些边反过来
写的时候注意的是先把所有的第一种和第二种边建出来，然后每次只用加上第一种边就好了
Code Display
inline void build1(vector<int> now){
int S1=-1,S2=-1;
for(auto t:now){
int s1=++tot,s2=++tot;
vec[t].push_back(s1); vec[s2].push_back(t+m);
if(~S1){
vec[S1].push_back(s1),vec[s2].push_back(S2);
vec[S1].push_back(t+m); vec[t].push_back(S2);
}
S1=s1,S2=s2;
} return;
}
inline void build2(vector<int> now){
int S1=-1,S2=-1;
for(auto t:now){
int s1=++tot,s2=++tot;
vec[s1].push_back(t)); vec[t+m].push_back(s2);
if(~S1){
vec[s1].push_back(S1); vec[S2].push_back(s2);
vec[t+m].push_back(S1); vec[S2].push_back(t);
}
S1=s1; S2=s2;
} return ;
}
Luogu6965 一题中把前后缀优化建图搬到了树上，需要建立上向树和下向树，那么在递归建树的时候传入 \(\rm last\) 表示父亲节点建出的最后一个点即可
之所以说“最后一个点” 是因为每个 \(\rm trie\) 树上节点所包含的点可能不止一个