CF786B Legacy 题解 线段树优化建图

· · 题解

题目传送门

题意

题解

先考虑暴力连边，发现时间复杂度达到了 O(n^2)。

考虑到区间连边，那么可以对于一个区间进行拆分。

我们很容易想到线段树。

考虑将线段树的节点作为代替一个区间的虚点。

显然我们需要两棵线段树，不然跑出来距离都是 0 了还跑啥。（（（

我们以左边线段树的叶子节点为实际的点。

用红线代表双向边，橙色代表向下的单向边，蓝色代表向上的单向边，紫色代表向右的单向边。

显然这是初始必须要连的边，同时这些边的边权为 0。

初始化时间复杂度 O(n)。

考虑操作 1。

直接实际的点连单向边即可。

单次操作时间复杂度 O(1)。

例如连 2 \to 3 这条边。

考虑操作 2。

点连区间，我们将区间剖分成线段树上的节点，然后实际的点向各个表示区间的点连接即可。

单次操作时间复杂度 O(\log n)。

例如 1 \to [5,8]。

考虑操作 3。

单次操作时间复杂度 O(\log n)。

区间连点，同样我们将区间剖分为线段树上的节点，然后表示区间的点连向实际的点即可。

例如 [1,4] \to 1。

最后合起来图就成了这样。

然后从原点对应的实点开始跑 Dijkstra 即可。

记得空间开大！记得开 long long！

空间复杂度上界 O(n+q\log n)。

时间复杂度上界 O(n\log^2 n)。

代码

const int N=5e5+5,D=5e5,INF=1e17;
int n,m,st,dis[N<<1],node[N];
bool vst[N<<1];
vector<pair<int,int> >es[N<<1];

#define mid ((l+r)>>1)
#define xl (x<<1)
#define xr (x<<1|1)

inline void build(int x,int l,int r){
    if(l==r){node[l]=x;return ;}
    es[x].pb(mp(0,xl));es[x].pb(mp(0,xr));
    es[xl+D].pb(mp(0,x+D));es[xr+D].pb(mp(0,x+D));
    build(xl,l,mid);build(xr,mid+1,r);
}

inline void add(int x,int l,int r,int L,int R,int v,int w,int op){
    if(L<=l&&r<=R){
        if(op==2) es[v].pb(mp(w,x));
        else es[x+D].pb(mp(w,v));
        return ;
    }
    if(L<=mid) add(xl,l,mid,L,R,v,w,op);
    if(R>mid) add(xr,mid+1,r,L,R,v,w,op);
}

inline void dijkstra(int s){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; 
    fill(dis,dis+(N<<1)+1,INF);dis[s]=0;q.push(mp(0,s));
    while(!q.empty()){
        int x=q.top().second,sum=q.top().first;
        q.pop();
        if(vst[x]) continue;
        vst[x]=1;
        for(re i=0;i<es[x].size();++i){
            int t=es[x][i].second,w=es[x][i].first;
            if(dis[t]>sum+w){
                dis[t]=sum+w;
                q.push(mp(dis[t],t));
            }
        }
    }
}

// ---------- Graph ---------- //

signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    rd(n);rd(m);rd(st);
    build(1,1,n);
    for(re i=1;i<=n;++i) es[node[i]].pb(mp(0,node[i]+D)),es[node[i]+D].pb(mp(0,node[i]));
    for(re i=1;i<=m;++i){
        int op,u,v,w,l,r;
        rd(op);
        if(op==1){
            rd(v);rd(u);rd(w);
            es[node[v]].pb(mp(w,node[u]));
        }
        else{
            rd(v);rd(l);rd(r);rd(w);
            add(1,1,n,l,r,node[v],w,op);
        }
    }
    dijkstra(node[st]);
    for(re i=1;i<=n;++i){
        if(dis[node[i]]==INF) cout<<"-1 ";
        else wr(dis[node[i]]),putchar(' ');
    }puts("");
    return 0;
}

// ---------- Main ---------- //