CodeForces - 786B Legacy（线段树优化建图）

传送门：CodeForces - 786B

思路分析

建两棵线段树，一棵叫$in$，一棵叫$out$
$in:$父亲往儿子连一条0的边
$out:$儿子往父亲连一条0的边
对于$u->[l,r]$的连边，$out$树上$u$的叶子节点往$in$树上对应的区间节点连一条有向边
对于$[l,r]->v$的连边，$out$树上对应的区间节点往$in$树上$v$叶子节点连一条有向边

AC代码

#include <bits/stdc++.h>
#define V vector
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) (x)&(-x)
#define sz(x) (int)(x).size()
#define each(x,a) for(auto& x:a)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const ll INF = 1e18;
const double PI = acos(-1);
const int N = 4e6+10;
const int M = 1e5+10;

int tot,inpos[N],outpos[N],vis[N];
ll dis[N];
V<pii>e[N];

void add(int u,int v,int w){
    e[u].pb(mp(v,w));
}

struct node{
    int l,r,mid,inid,outid;
}tree[M<<2];

#define ls x<<1
#define rs x<<1|1

void build(int x,int l,int r){
    tree[x] = {l,r,(l+r)/2,++tot,++tot};
    if(l==r){
        inpos[l] = tree[x].inid;
        outpos[l] = tree[x].outid;
        add(inpos[l],outpos[l],0);
        return ;
    }
    int mid = tree[x].mid;
    build(ls,l,mid);
    build(rs,mid+1,r);
    add(tree[x].inid,tree[ls].inid,0);
    add(tree[x].inid,tree[rs].inid,0);
    add(tree[ls].outid,tree[x].outid,0);
    add(tree[rs].outid,tree[x].outid,0);
}

void modify(int x,int l,int r,int v,int w,int type){
    if(l<=tree[x].l && tree[x].r<=r){
        if(type == 2){
            add(outpos[v],tree[x].inid,w);
        }else{
            add(tree[x].outid,inpos[v],w);
        }
        return ;
    }
    int mid = tree[x].mid;
    if(l<=mid) modify(ls,l,r,v,w,type);
    if(r>mid) modify(rs,l,r,v,w,type);
}

void dij(int s){
    for(int i=1;i<N;i++) dis[i] = INF;
    mem(vis,0);
    dis[inpos[s]] = 0;
    priority_queue<pair<ll,int>>q;
    q.push(mp(0LL,inpos[s]));
    while(!q.empty()){
        int u = q.top().se;
        q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        each(x,e[u]){
            int v = x.fi;
            int w = x.se;
            if(dis[v]>dis[u]+w){
                dis[v] = dis[u]+w;
                q.push(mp(-dis[v],v));
            }
        }
    }
}

signed main() {

#ifdef xiaofan
    clock_t stTime = clock();
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
/*==========================begin============================*/
    IOS;
    int n,m,s;
    cin>>n>>m>>s;
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op,l,r,v,w;
        cin>>op;
        if(op==1){
            cin>>l>>r>>w;
            add(outpos[l],inpos[r],w);
        }
        else{
            cin>>v>>l>>r>>w;
            modify(1,l,r,v,w,op);
        }
    }
    dij(s);
    for(int i=1;i<=n;i++) {
        if(dis[outpos[i]]==INF) dis[outpos[i]] = -1;
        cout<<dis[outpos[i]]<<" ";
    }



/*===========================end=============================*/
#ifdef xiaofan
    cerr << "Time Used:" << clock() - stTime << "ms" <<endl;
#endif
    return 0;
}