优化建图

写 \(2-SAT\) 时刷到的，发现好像一点不会，学习下。

1. 线段树优化建图

当一个点与一段区间连边时，暴力连是 \(O(n^2)\) 的。
因为线段树有一个肥肠优秀的性质，一个区间最多被分为 \(O(logn)\) 个节点。
so，我们可以把区间当成放到线段树上，这样是 \(O(nlogn)\) 的。
具体的，我们建立一个入线段树与出线段树，初始都连长度为 \(0\) 的边。

建图时根据区间建即可。

• 当区间到区间建图时，可以建立一个 虚点，让 区间->虚点p->区间，复杂度不变，常数较大。

肥肠的神奇啊。

I CF786B Legacy

裸题，建树建边即可，详见代码

#include <bits/stdc++.h> 
using namespace std;
//线段树优化建图模版 
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define inf 1e18
//神tm pair要开longlong!!! const int N = 2e6+10,K = 5e5;int n,q,s;
struct made{int ver,nx;ll ed;
}e[N<<1];
int hd[N],tot;
void add(int x,int y,ll z){tot++;e[tot].nx = hd[x],e[tot].ver = y,e[tot].ed = z,hd[x] = tot;
}int a[N];
void build(int p,int l,int r){if(l == r)return a[l] = p,void();add(p<<1,p,0),add(p<<1|1,p,0);add(p+K,(p<<1)+K,0),add(p+K,(p<<1|1)+K,0);int mid = l + r >> 1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
void add(int p,int x,int L,int R,int l,int r,ll z,bool op){if(L <= l && r <= R)return op?add(a[x],p+K,z) : add(p,a[x]+K,z),void();int mid = l + r >> 1;if(L <= mid)add(p<<1,x,L,R,l,mid,z,op);//if(R > mid)add(p<<1|1,x,L,R,mid+1,r,z,op);
}//线段树建 入树(p) 与 出树(p+K)bool v[N];
ll d[N];
void dij(int u){memset(v,0,sizeof v);for(int i = 1;i <= 2*K;i++)d[i] = inf;priority_queue<pii,vector<pii>,greater<pii> >q;d[u] = 0;q.push(mp(0,u));while(!q.empty()){int x = q.top().se;q.pop();if(v[x])continue;v[x] = 1;for(int i = hd[x];i;i = e[i].nx){int y = e[i].ver;ll z = e[i].ed;if(d[y] > d[x] + z){d[y] = d[x] + z;q.push(mp(d[y],y));}}}
}//dijdij
int main(){scanf("%d%d%d",&n,&q,&s);build(1,1,n);for(int i = 1;i <= n;i++)add(a[i]+K,a[i],0);for(int i = 1;i <= q;i++){int op,x,y,l,r;ll z;scanf("%d%d",&op,&x);if(op == 1)scanf("%d%lld",&y,&z),add(a[x],a[y]+K,z);else if(op == 2)scanf("%d%d%lld",&l,&r,&z),add(1,x,l,r,1,n,z,1);else scanf("%d%d%lld",&l,&r,&z),add(1,x,l,r,1,n,z,0);}dij(a[s]);for(int i = 1;i <= n;i++){if(d[a[i]] == inf)printf("-1 ");else printf("%lld ",d[a[i]]);}printf("\n");return 0;}

II P6348 [PA2011] Journeys
裸题，只是区间向区间连边

代码

III P9520 [JOISC2022] 监狱
非常好的一道题。

我们可以发现一个性质

• 如果一个方案满足条件，则必然存在一种情况使每个囚犯都独立的由起点走向终点。
• 证明：如果一个囚犯走到一半，另一个囚犯再走这种方案满足条件，则两个囚犯独立走也一定满足条件。

所以每个囚犯只需自己走即可。
我们考虑囚犯的先后顺序，定义有向边 \((x,y)\) 代表 \(x\) 号囚犯需要第 \(y\) 号囚犯先走，才可以满足条件。
可以发现：

• 一个囚犯 \(i\)，若有囚犯 \(j\) 的起点在囚犯 \(i\) 的路径上时，需要连接 \(i \rightarrow j\)
• 类似的，一个囚犯 \(i\)，若有囚犯 \(j\) 的终点在囚犯 \(i\) 的路径上时，需要连接 \(j \rightarrow i\)

最后只需判断是否存在环即可。

但是这样的边数为 \(O(n^2)\)，考虑优化建图。
因为我们判环可以 \(O(m)\) 判环，所以可以直接 树剖加线段树优化建图，直接 \(O(nlogn^2)\)。
能过。

不过在树上也可以用倍增优化建图或前后缀优化建图。
都可以把边数优化到 \(O(nlogn)\)。

• 倍增优化的常数有些大，导致其实跑的差不多快

代码(树剖+线段树)

2. 前后缀优化建图

当我们需要一个集合内的点互相连边时，可优化到 \(O(n)\)。

I P6378 [PA2010] Riddle
可以发现，每条边至少选一个点，每个部分只能选一个点。

这是一个 \(2 - SAT\) 问题，只需要考虑 \(!p \rightarrow q\) 和 \(p \rightarrow !q\) 即可。
但这样我们发现边数是 \(O(n^2)\) 的，用 \(tarjan\) 找环的复杂度也是 \(O(n^2)\) 的。

需要优化建图。
为了简化建边，我们需要一些多余的点，叫做虚点。
我们可以首先把集合拉成一个序列，我们可以类似于前缀和一样建一个前缀节点，第 \(i\) 个前缀节点连着前 \(i\) 个点。
这样我们只需要多建 \(n\) 个点与 \(2n\) 条边就可完成建边。类似的，我们也同样建 \(n\) 个后缀节点。
这样第 \(i\) 个点想要连接其他的点只需要连接第 \(i-1\) 个前缀节点与第 \(i+1\) 个后缀节点 两条边即可。

这样一共有 \(8n\) 条边，复杂度线性。
跑下 \(2-SAT\) 即可。

代码

II P5344 【XR-1】逛森林