线段树优化建图
- 用途:处理区间连边
- 做法:建两颗线段树，一颗处理区间的入边，另一颗处理出边(如果用一颗线段树的话，边权就都为0了)
例题: Legacy
板子题，直接看代码
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
const int N = 1e6 + 10;
struct EDGE{int to,next,w;}edge[N<<1];
int head[N],cnt;
auto add = [](int u,int v,int w) -> void {edge[++cnt] = {v,head[u],w};head[u] = cnt;};
int t1[N<<2],t2[N<<2],tot;
void build(int k,int l,int r){
if(l == r){t1[k] = t2[k] = l;return;}//将叶子节点设为原点
int mid = (l+r)>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
t2[k] = ++tot;t1[k] = ++tot;
//出树建图
add(t2[k<<1],t2[k],0);
add(t2[k<<1|1],t2[k],0);
//入树建图
add(t1[k],t1[k<<1],0);
add(t1[k],t1[k<<1|1],0);
}
void updateIn(int k,int l,int r,int L,int R,int u,int w){
if(L <= l && r <= R)return add(u,t1[k],w);//当前区间已经覆盖
int mid = (l+r)>>1;
if(L <= mid) updateIn(k<<1,l,mid,L,R,u,w);
if(R > mid) updateIn(k<<1|1,mid+1,r,L,R,u,w);
}
void updateOut(int k,int l,int r,int L,int R,int u,int w){
if(L <= l && r <= R) return add(t2[k],u,w);
int mid = (l+r)>>1;
if(L <= mid) updateOut(k<<1,l,mid,L,R,u,w);
if(R > mid) updateOut(k<<1|1,mid+1,r,L,R,u,w);
}
#define pli pair<ll,int>
#define mk make_pair
ll dist[N];
bitset<N> vis;
void dijkstra(int s){
memset(dist,0x3f,sizeof dist);
vis.reset();
dist[s] = 0;
priority_queue<pli,vector<pli>,greater<pli> > q;
q.push(mk(0,s));
while(q.size()){
int x = q.top().second;q.pop();
if(vis[x]) continue;
vis[x] = true;
for(int i = head[x]; i;i = edge[i].next){
int y = edge[i].to;
if(dist[y] > dist[x] + edge[i].w){
dist[y] = dist[x] + edge[i].w;
q.push(mk(dist[y],y));
}
}
}
}
int n,q,s;
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>q>>s;
tot = n;//提前将前n个点留出来
build(1,1,n);
for(int i = 1;i <= q; ++i){
int op;cin>>op;
if(op == 1){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
}
if(op == 2){
int u,l,r,w;
cin>>u>>l>>r>>w;
updateIn(1,1,n,l,r,u,w);
}
if(op == 3){
int v,l,r,w;
cin>>v>>l>>r>>w;
updateOut(1,1,n,l,r,v,w);
}
}
dijkstra(s);
for(int i = 1;i <= n; ++i){
cout<<(dist[i] == dist[0]?-1:dist[i])<<' ';
}
}