CF786B-Lagacy

线段树优化最短路建边模版。

要同时建立两棵线段树，由于是动态开点线段树，可以只开一个tr结构体数组。一个线段树由区间（顶部）向下建边，另一个反过来建边，这样可以保证初始的时候节点之间两两不能互相到达。

动态开点要从n+1开始开点，最底部的节点仍然对应原来节点的编号，这样便于加边（当然不这么处理也可以写）。两棵线段树的最底部的节点是一致的。

加边的时候这棵树并不需要自顶向下做什么操作，实际上只是套了一个线段树的壳子来减少边的数量而已，实际上是在两棵线段树构成的图上跑最短路。对于操作一，直接加边即可。对于后两种，由于我们并不能O(1)给出一个区间对应的一个或多个节点，所以需要利用线段树查询的方式找到区间对应的节点，然后建立单向边。

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
#define mid ((lo+ro)>>1)
const int maxn=4e5+10;
const ll inf=1e16;
struct xnode{
    int lo;int ro;
}tr[maxn*10];
int tot,n,q,s,rtin,rtou;
struct node{
    int v;ll w;
};
vector<node> all[maxn*10];
struct qnode{
    int pos;ll dis;
};
struct cmp{
    bool operator()(const qnode &a1,const qnode &a2){return a1.dis>a2.dis;}
};
priority_queue<qnode,vector<qnode>,cmp> k1;
ll dis[maxn*10];
bool vis[maxn*10];
void add1(int u,int v,ll w){
    all[u].push_back((node){v,w});
}
void buildin(int &now,int lo,int ro){
    now=++tot;
    if(lo==ro){now=lo;return;}
    int mid1=(lo+ro)/2;
    buildin(tr[now].lo,lo,mid1);
    buildin(tr[now].ro,mid+1,ro);
    add1(now,tr[now].lo,0);
    add1(now,tr[now].ro,0);
}
void buildou(int &now,int lo,int ro){
    now=++tot;
    if(lo==ro){now=ro;return;}
    int mid1=(lo+ro)/2;
    buildou(tr[now].lo,lo,mid1);
    buildou(tr[now].ro,mid1+1,ro);
    add1(tr[now].lo,now,0);
    add1(tr[now].ro,now,0);
}
void upd(int &now,int lo,int ro,int lr,int rr,int zhi,int tp,int pos){
    if(lr>=lo&&rr<=ro){
        if(tp==2) add1(pos,now,zhi);
        else add1(now,pos,zhi);
        return;
    }   
    int mid1=(lr+rr)/2;
    if(mid1>=lo) upd(tr[now].lo,lo,ro,lr,mid1,zhi,tp,pos);
    if(mid1<ro) upd(tr[now].ro,lo,ro,mid1+1,rr,zhi,tp,pos);
}
int main(){
    ios;fre();
    cin>>n>>q>>s;
    tot=n;
    buildin(rtin,1,n);
    buildou(rtou,1,n);
    for(int i=1;i<=q;i++){
        int tmp;cin>>tmp;
        if(tmp==1){
            int u,v,w;cin>>u>>v>>w;
            add1(u,v,w);
        }
        else{
            int r,lo,ro,w;cin>>r>>lo>>ro>>w;
            upd(tmp==2?rtin:rtou,lo,ro,1,n,w,tmp,r);
        }
    }
    for(int i=1;i<=tot;i++) dis[i]=inf;
    dis[s]=0;
    k1.push((qnode){s,0});
    while(!k1.empty()){
        int tmp=k1.top().pos;k1.pop();
        if(vis[tmp]) continue;
        vis[tmp]=1;
        for(int i=0;i<all[tmp].size();i++){
            int v=all[tmp][i].v,w1=all[tmp][i].w;
            if(vis[v]) continue;
            if(dis[v]>dis[tmp]+w1){
                dis[v]=dis[tmp]+w1;
                k1.push((qnode){v,dis[v]});
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(dis[i]==inf) cout<<-1<<' ';
        else cout<<dis[i]<<' ';
    }
    return 0;
}