线段树优化建图详解——区间连边之技巧，吊打紫题之利器 我们从⼀道例题开始。
CF786B
Description
Solution
朴素解法: 暴⼒连边+最短路
对于每次连边操作，我们逐⼀连边，最后在图上跑⼀遍单源最短路径算法即可。
正解: 线段树优化建图
线段树有⼀个⾮常优美的性质: 区间可以被映射成线段树上的许多连续的区间，且这些区间的数量不超过。
我们要巧妙运⽤这个性质——我们是否可以将每⼀个连边的区间映射到线段树上的个节点，然后只向这个节点连边呢？答案是可以的。我们建⽴两棵线段树，⼀个线段树往内连边(简称为⼊树)，另⼀个线段树往外连边(简称为出树)。每棵树的叶节点对应图中⼀个的真实节点。同时，两棵树中对应的叶节点连⼀条边权为的有向边(即下图中五彩缤纷的那些边)。同⼀棵树中的⽗节点与孩⼦节点也要连⼀条边权为的有向边。 O (n log(n ))22[l ,r ]⌈log n ⌉[l ,r ]log log 00
对于每次连边操作，我们只向个节点连⼀条有向边，边权为
。
上图表⽰⼀个形如“从号节点向区间中的点分别连⼀条边”的第⼆类操作。第三类操作同理。第⼀类操作直接将对应的叶节点连边。最后我们跑⼀遍单源最短路(Dijkstra)即可。
注意，这⾥的最短路的“源”是出树中表⽰区间的叶节点。
由于边数为级别，所以总时间复杂度为。
Code
#include <bits/stdc++.h>
#define int long long
#define inf 200000000000007
using namespace std ;
const int maxl =100005,maxg =20;
int read (){
log w 1[3,8][1,1]O (n log n )O (n log n log(n log n ))≈O (n log n )2
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=-w;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^'0');ch=getchar();} return s*w;
}
int n,m,s,blo,opt,u,l,r,w,cnt=0;
int head[8*maxl],itree[4*maxl],otree[4*maxl],pos[maxl];
int dis[8*maxl],vis[8*maxl];
struct edge{int nxt,to,dis;}e[4*maxg*maxl];//边数可能较多
防身报警器struct node{
int dis,pos;
bool operator<(const node &x)const{return x.dis<dis;}
};
void add_edge(int u,int v,int w){
cnt++;
e[cnt].to=v,e[cnt].dis=w,e[cnt].nxt=head[u];
head[u]=cnt;
}
void build_itree(int l,int r,int rt){
if(l==r){
pos[l]=rt;
add_edge(rt+blo,rt,0),add_edge(rt,rt+blo,0);
return;
}
int mid=(l+r)>>1;
add_edge(rt,2*rt,0),build_itree(l,mid,2*rt);
add_edge(rt,2*rt+1,0),build_itree(mid+1,r,2*rt+1);
}
void build_otree(int l,int r,int rt){
if(rt!=1)add_edge(blo+rt,blo+(rt/2),0);
if(l==r)return;
int mid=(l+r)>>1;
build_otree(l,mid,2*rt);
build_otree(mid+1,r,2*rt+1);
}
void tree_edge(int nl,int nr,int l,int r,int rt,int link_pos,int ww,int k){ if(nl<=l&&r<=nr){
if(k==0)add_edge(link_pos+blo,rt,ww);
索道安装
else add_edge(rt+blo,link_pos,ww);
return;
}
int mid=(l+r)>>1;
if(nl<=mid)tree_edge(nl,nr,l,mid,2*rt,link_pos,ww,k);
if(nr>mid)tree_edge(nl,nr,mid+1,r,2*rt+1,link_pos,ww,k);
}
std::priority_queue<node> q;
void dijkstra(){
q.push((node){0,s});
dis[s]=0;
while(!q.empty()){
int p().pos;
q.pop();
if(vis[now])continue;
vis[now]=1;
for(int i=head[now];i;i=e[i].nxt){
int y=e[i].to;
if(dis[y]>dis[now]+e[i].dis){
dis [y ]=dis [now ]+e [i ].dis ;
if (!vis [y ]) q .push ((node ){dis [y ],y });
}
}
}
}
signed main (){
n =read (),m =read (),s =read ();blo =4*n ;
build_itree (1,n ,1);
build_otree (1,n ,1);//给树中的每个节点⼀个统⼀的编号
for (int i =1;i <=m ;i ++){
opt =read (),u =read ();
if (opt ==1){
l =read (),w =read ();
数显计数器
tree_edge (l ,l ,1,n ,1,pos [u ],w ,0);
}
else if (opt ==2){
l =read (),r =read (),w =read ();
tree_edge (l ,r ,1,n ,1,pos [u ],w ,0);
}
else if (opt ==3){
l =read (),r =read (),w =read ();
tree_edge (l ,r ,1,n ,1,pos [u ],w ,1);
}
}
s =blo +pos [s ];
for (int i =1;i <=8*n ;i ++) dis [i ]=inf ;
dijkstra ();
for (int i =1;i <=n ;i ++){
if (dis [pos [i ]]>=inf ) dis [pos [i ]]=-1;
}
for (int i =1;i <=n ;i ++) printf ("%lld ",dis [pos [i ]]);
return 0;
}
⼀个⼩扩展: 第四类操作
第四类操作是区间向区间连边，即中的每个节点向中的每个节点连⼀条边权为的边。
对于这⼀种新的操作我们该怎么办呢？不难想到，我们可以新建⼀个虚点，然后就变成了“向连边”与“向连边”，分别处理即可。
显然第四类操作并没有对时间复杂度有太⼤的影响(就是常数变⼤了好多……)，依然是。
例题: P5025
自动埋钉机
Description
秸秆腐熟剂
杨木皮子Solution
算法⼀: 套路，朴素，时间复杂度，空间复杂度对于两个能够互相引爆的节点我们连⼀条边。
[l ,r ]11[l ,r ]22w p [l ,r ]11p p [l ,r ]22O (n log n )2O (n )2O ()32n 2
显然，所有第个能够引爆的就是所有从出发能够到达的。这是⼀个可达性统计问题。我们采⽤去转移即可。算法⼆: 连边的性质与线段树优化建图
不难发现，第个节点连向的所有节点⼀定在⼀个连续的区间内。
于是，我们可以对于每⼀个⼆分出和然后线段树优化建图即可。最后再跑⼀遍可达性统计。
时间复杂度与空间复杂度不变。
算法三: ⼩性质得到正解
考虑第个节点可达的节点映射下来⼀定是⼀个区间。
所以我们并不需要这种⼤空间&⼤时间复杂度写法，我们只需要求出从第个节点能够到达的区间的左右端点即可，区间长度即为可达的数量。这可以通过缩点+上求出。
时间复杂度被我们优化成了。
Code
#include <bits/stdc++.h>
#define ll long long
#define inf 2000000007
using namespace std ;
const int maxl =500005,maxt =1500005,maxg =19,mod =1e9+7;
ll read (){
ll s =0,w =1;char ch =getchar ();
while (ch <'0'||ch >'9'){if (ch =='-') w =-w ;ch =getchar ();}
while (ch >='0'&&ch <='9'){s =(s <<1ll )+(s <<3ll )+(ch ^'0');ch =getchar ();}
return s *w ;
}
int n ,tot ,blo ,len ,cnt ,nt ;ll ans =0;
int head [maxt ],tree [maxl *2][2],dfn [maxt ],low [maxt ],s [maxt ];
int fa [maxt ],lm [maxt ],rm [maxt ],inde [maxt ];
ll a [maxl ],b [maxl ];
bitset <maxt > vis ,is_fa ;
queue <int > q ;
map <pair <int ,int >,bool > ma ;
struct node {int x ,y ;}edge_lis [2*maxl +maxl *maxg ];
struct edge {int nxt ,to ;}e [2*maxl +maxl *maxg ];
void add_edge (int u ,int v ){
cnt ++;
e [cnt ].to =v ,e [cnt ].nxt =head [u ],head [u ]=cnt ;
}
void clear_edges (){
cnt =0;
for (int i =1;i <=3*n ;i ++) head [i ]=0;
}
int build_tree (int l ,int r ,int rt ){
rt =++tot ;
if (l ==r ){
add_edge (rt ,2*n +l );
add_edge (2*n +l ,rt );
return rt ;
}
int mid =(l +r )>>1;
tree [rt ][0]=build_tree (l ,mid ,0);
tree [rt ][1]=build_tree (mid +1,r ,0);
add_edge (rt ,tree [rt ][0]);i i bitset i [L ,R ]i L R i bitset i DAG DP O (n log n )
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议