关于线段树优化建图
对于存在一些单点连向区间或区间连向单点的边，且直接暴力连边会爆炸的题目，就可以考虑使用线段树优化建图。
边数量的规模将会是 \(n \log n+a\)。
例题
题目链接。
从 \(s\) 到 \(t\) 的最短路就是模板。如果暴力建边，最坏情况下需要建的边在 \(n^2\) 级别，显然是不可能的。
考虑线段树优化建图。对于第 \(1\) 种建边方式，只能是直接将 \(u,v\) 连边。而对于 \(2,3\) 两种建边方式，开两棵线段树分别维护单点连向区间的边与区间连向单点的边。第 \(1\) 棵线段树的边均为父亲连向儿子，第 \(2\) 棵线段树的边均为儿子连向父亲。
对于第 \(2\) 种建边方式，若线段树上点 \(u\) 包含的区间 \([u_l,u_r]\) 均在区间 \([l,r]\) 里，则 \([u_l,u_r]\) 中任意一个点都会与 \(v\) 连边。则将 \(v\) 在第 \(2\) 棵线段树上的点与 \(u\) 连边。第 \(3\) 种 和第 \(2\) 种情况类似。
两棵线段树中对应的叶子节点表示的节点是一样的，所以也要将它们连边。
可以看一下 OI Wiki 的图。
代码如：
const int M=5e5+1;
il void add(int a,int b,int c){
ne[++idx]=h[a],e[idx]=b,w[idx]=c,h[a]=idx;
}
il void build(int now,int l,int r){
tr[now].l=l,tr[now].r=r;
if(l==r) return id[l]=now,void(0);
int mid=l+r>>1;
add(now,now<<1,0),add(now,now<<1|1,0);//第1棵线段树
add((now<<1)+M,now+M,0),add((now<<1|1)+M,now+M,0);//第2棵线段树
build(now<<1,l,mid),build(now<<1|1,mid+1,r);
return ;
}
il void Add(int now,int l,int r,int v,int w,bool flag){
if(tr[now].l>=l&&tr[now].r<=r){
if(!flag) add(id[v]+M,now,w);//点连向区间
else add(now+M,id[v],w);//区间连向点
return ;
}
int mid=tr[now].l+tr[now].r>>1;
if(l<=mid) Add(now<<1,l,r,v,w,flag);
if(mid<r) Add(now<<1|1,l,r,v,w,flag);
return ;
}
il void init(){
for(re int i=1;i<=n;++i)
add(id[i],id[i]+M,0),
add(id[i]+M,id[i],0);
return ;
}
然后这道题就是建完图之后跑一个 dij 求一个单源最短路。
注：起点将是第 \(2\) 棵线段树的叶子节点。
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")
namespace yzqwq{
il int read(){
int x=0,f=1;char ch=gc;
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
return x*f;
}
il int qmi(int a,int b,int p){
int ans=1;
while(b){
if(b&1) ans=ans*a%p;
a=a*a%p,b>>=1;
}
return ans;
}
il auto max(auto a,auto b){return (a>b?a:b);}
il auto min(auto a,auto b){return (a<b?a:b);}
il int gcd(int a,int b){
if(!b) return a;
return gcd(b,a%b);
}
il int lcm(int a,int b){
return a/gcd(a,b)*b;
}
il void exgcd(int a,int b,int &x,int &y){
if(!b) return x=1,y=0,void(0);
exgcd(b,a%b,x,y);
int t=x;
x=y,y=t-a/b*x;
return ;
}
mt19937 rnd(time(0));
}
using namespace yzqwq;
const int N=3e6+10,M=5e5+1;
int n,m,s,id[N];
int ne[N],e[N],w[N],h[N],idx;
struct Tree{
int l,r;
}tr[N];
int vis[N],dis[N];
il void add(int a,int b,int c){
ne[++idx]=h[a],e[idx]=b,w[idx]=c,h[a]=idx;
}
il void build(int now,int l,int r){
tr[now].l=l,tr[now].r=r;
if(l==r) return id[l]=now,void(0);
int mid=l+r>>1;
add(now,now<<1,0),add(now,now<<1|1,0);//第1棵线段树
add((now<<1)+M,now+M,0),add((now<<1|1)+M,now+M,0);//第2棵线段树
build(now<<1,l,mid),build(now<<1|1,mid+1,r);
return ;
}
il void Add(int now,int l,int r,int v,int w,bool flag){
if(tr[now].l>=l&&tr[now].r<=r){
if(!flag) add(id[v]+M,now,w);//点连向区间
else add(now+M,id[v],w);//区间连向点
return ;
}
int mid=tr[now].l+tr[now].r>>1;
if(l<=mid) Add(now<<1,l,r,v,w,flag);
if(mid<r) Add(now<<1|1,l,r,v,w,flag);
return ;
}
il void init(){
for(re int i=1;i<=n;++i)
add(id[i],id[i]+M,0),
add(id[i]+M,id[i],0);
return ;
}
il void dij(){
priority_queue<pii,vector<pii>,greater<pii>> qu;
memset(dis,0x3f,sizeof(dis)),
memset(vis,0,sizeof(vis));
dis[id[s]+M]=0,qu.push({0,id[s]+M});
while(!qu.empty()){
pii now=qu.top();qu.pop();
if(vis[now.y]) continue;
vis[now.y]=1;
for(re int i=h[now.y];i;i=ne[i]){
int j=e[i];
if(dis[j]>dis[now.y]+w[i])
dis[j]=dis[now.y]+w[i],
qu.push({dis[j],j});
}
}
return ;
}
il void solve(){
n=rd,m=rd,s=rd;
build(1,1,n),init();
for(re int i=1;i<=m;++i){
int op=rd,v=rd,u,l,r,w;
if(op==1){
u=rd,w=rd;
add(id[v]+M,id[u],w);
}
else if(op==2){
l=rd,r=rd,w=rd;
Add(1,l,r,v,w,0);
}
else{
l=rd,r=rd,w=rd;
Add(1,l,r,v,w,1);
}
}
dij();
for(re int i=1;i<=n;++i) printf("%lld ",dis[id[i]]>=1e18?-1:dis[id[i]]);
return ;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int t=1;while(t--)
solve();
return 0;
}