线段树优化建图 学习笔记&模板

· · 个人记录

模板题 - 题面：Link

思路

如果只有 u \rightarrow v，我们暴力建图就行了；但是，对于 u \rightarrow [l,r]，我们考虑用一个线段树维护有向边的终点的集合，这样任意的 [l,r] 都可以用这个集合中的线段拼成。对于每个 [l,r]，假设它由 k 个区间 [l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k] 构成，节点编号分别 p_1,p_2,\cdots,p_k。那么 \forall i \in [1,k]，直接 u \rightarrow p_i 连边即可。

对于线段树内部，父亲向儿子连一条长度为 0 的边即可。

复杂度分析：

线段树单次查询 / 修改最多涉及 \log n 个节点，共 m 次，最多 m \log n 条边。跑 Dijkstra 最短路时间复杂度是 O((V+E) \log E)，这里 V=n \log n,E=m \log n，时间复杂度 O(n \log n \log(m \log n))，由于 n,m 同级可以看成 O(n \log^2 n) 的复杂度，可以通过。

代码

#include <bits/stdc++.h>
#define cint const int
using namespace std;
cint MAXN=100005,MAXLOG=(MAXN<<1)*25;
vector<pair<int,int> > E[MAXLOG];
int dis[MAXLOG];
bool vis[MAXLOG];

int tot,num[MAXN];
struct Tree{int ls,rs;}tr[MAXLOG];
inline void add(cint &u,cint &v,cint &w){
    E[u].push_back(make_pair(v,w));
}
void build(int &p,int l,int r){
    if(!p) p=++tot;
    if(l==r){
        num[l]=p; // num[i] 意思是表示 [i,i] 区间（即 i 这个点）的线段树节点的编号
        return;
    }
    int mid=(l+r)>>1;
    build(tr[p].ls,l,mid); // 继续向下 
    build(tr[p].rs,mid+1,r);
    add(p,tr[p].ls,0); // 父亲向儿子加边 
    add(p,tr[p].rs,0);
}
void update(int p,int l,int r,int st,int en,int u,int w){ // u 向 [st,en] 加长为 w 的边
    if(l>en || r<st) return;
    if(st<=l && r<=en){
        add(u,p,w); // 被包含在 [l,r] 内的区间，对答案有贡献，加边并 return 
        return;
    }
    int mid=(l+r)>>1;
    update(tr[p].ls,l,mid,st,en,u,w);
    update(tr[p].rs,mid+1,r,st,en,u,w); 
}

void Dijkstra(int root){ // 标准の Dijkstra 
    memset(dis,0x3f,sizeof(dis));
    priority_queue<pair<int,int> > q;
    dis[root]=0; q.push(make_pair(0,root));
    while(!q.empty()){
        int u=q.top().second; q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=0;i<E[u].size();i++){
            int v=E[u][i].first,w=E[u][i].second;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(make_pair(-dis[v],v));
            }
        }
    }
}
int main(){
    int n,m,root=0; cin>>n>>m;
    build(root,1,n);
    for(int i=1;i<=m;i++){
        int op,u; cin>>op>>u;
        if(op==1){
            int v,w; cin>>v>>w;
            update(root,1,n,v,v,num[u],w);
        }
        else{
            int l,r,w; cin>>l>>r>>w;
            update(root,1,n,l,r,num[u],w);
        }
    }
    Dijkstra(num[1]);
    for(int i=1;i<=n;i++){
        if(dis[num[i]]==1061109567) cout<<"-1 ";
        else cout<<dis[num[i]]<<" ";
    }
    return 0;
}