CF786B Legacy 线段树优化建图

问题描述

CF786B

LG-CF786B

题解

线段树优化建图

线段树的一个区间结点代表 \([l,r]\) 区间点。

然后建立区间点的时候就在线段树上建边，有效减少点的个数，从而提高时空效率。

优质题解传送门

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

#define int long long

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=100100;
int INF=0x3f3f3f3f3f3f3f3fll;

#define pii(x,y) make_pair(x,y)

#define mid ((l+r)>>1)
#define lfc (x<<1)
#define rgc ((x<<1)|1)


vector < pair < int , int > > e[maxn*10];
int n,T,S;
int cnt,out[maxn<<2],in[maxn<<2];

void build(int x,int l,int r){
    if(l==r){
        out[x]=in[x]=l;return;
    }
    build(lfc,l,mid);build(rgc,mid+1,r);
    out[x]=++cnt,in[x]=++cnt;
    e[out[lfc]].push_back(pii(out[x],0));
    e[out[rgc]].push_back(pii(out[x],0));
    e[in[x]].push_back(pii(in[lfc],0));
    e[in[x]].push_back(pii(in[rgc],0));
}

int L,R,st,val;

void change_in(int x,int l,int r){
    if(L<=l&&r<=R){
        e[st].push_back(pii(in[x],val));return;
    }
    if(r<L||R<l) return;
    change_in(lfc,l,mid);change_in(rgc,mid+1,r);
}

void change_out(int x,int l,int r){
    if(L<=l&&r<=R){
        e[out[x]].push_back(pii(st,val));return;
    }
    if(r<L||R<l) return;
    change_out(lfc,l,mid);change_out(rgc,mid+1,r);
}

int dis[maxn*10];
priority_queue< pair <int,int> > q;

bool vis[maxn*10];

void dijkstra(){
    memset(dis,0x3f,sizeof(dis));dis[S]=0;
    q.push(pii(0,S));
    while(!q.empty()){
        int x=q.top().second;q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(auto &i:e[x]){
            int y=i.first;
            if(y==0) continue;
            if(i.second+dis[x]<dis[y]){
                dis[y]=dis[x]+i.second;
                q.push(pii(-dis[y],y));
            }
        }
    }
}

signed main(){
    read(n);read(T);read(S);
    cnt=n;build(1,1,n);
    while(T--){
        int op;read(op);
        if(op==1){
            int aa,bb,cc;read(aa);read(bb);read(cc);
            e[aa].push_back(pii(bb,cc));
        }
        else if(op==2){
            int aa,bb,cc,dd;read(aa);read(bb);read(cc);read(dd);
            L=bb,R=cc,st=aa,val=dd;change_in(1,1,n);
        }
        else{
            int aa,bb,cc,dd;read(aa);read(bb);read(cc);read(dd);
            L=bb,R=cc,st=aa,val=dd;change_out(1,1,n);
        }
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        printf("%lld%c",(dis[i]==INF)?-1:dis[i]," \n"[i==n]);
    }
    return 0;
}