CF786B Legacy 题解

题意：

\(n\) 个结点， \(q\) 次操作，问操作后从 \(s\) 出发的单源最短路

操作如下

输入 1 u v w 表示 \(u\) 到 \(v\) 连一条有向边

输入 2 u l r w 表示 \(u\) 到 \([l,r]\) 的每个结点连一条有向边

输入 3 u l r w 表示 \([l,r]\) 的每个结点向 \(u\) 连一条有向边

对于 \(100\%\) 的数据，\(1\le n,q \le 10^5\)，\(1\le w \le 10^9\)

线段树优化建图的板子

考虑建两棵线段树，分别称为「入树」和「出树」

入树的父节点向子结点连一条边权为 \(0\) 的有向边

出树的子节点向父结点连一条边权为 \(0\) 的有向边

两棵树的叶子结点均表示原图中的点

这样每次区间的连边，我们直接在线段树上把管理对应区间的结点当作 \(v\) 即可

具体地，

把 \(u\) 到 \([l,r]\) 的每个结点连一条有向边

我们只要找出在入树上对应的结点，把出树中的 \(u\) 向这些结点都连一条有向边就行了
把 \([l,r]\) 的每个结点向 \(u\) 连一条有向边

我们只要找出在出树上对应的结点，把这些结点都向入树中的 \(u\) 连一条有向边就行了

这么说很抽象，给张图大家就懂了 made by diagrams

可以证明，这样修改的复杂度为 \(O(\log n)\)

总时间复杂度 \(O(n\log n + q \log n)\)

注意要记录结点 \(i\) 对应入树的叶子结点的编号，这两个是不一样的！

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
#include <bitset>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define DEBUG puts("-------------")
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(1e5+15))

const int D=5e5+15; // 两棵线段树的分界点
int n,m,s,d[N*10+255],a[N*10+255]; // a是结点编号对应的线段树叶子结点的编号
bitset<N*10+255> vis;
struct node1{int v,w;}; // 边
struct show_l_r{int l,r;}tr[N<<2]; // 辅助树
vector<node1> g[N*10+255]; // 两棵线段树
struct node2{int u,dis;};
bool operator<(node2 a,node2 b){return a.dis>b.dis;}
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
void build(int l,int r,int at)
{
    tr[at].l=l; tr[at].r=r;
    if(l==r) return a[l]=at, void(0);
    int mid=(l+r)>>1;
    g[at].push_back({ls(at),0});
    g[at].push_back({rs(at),0});
    g[ls(at)+D].push_back({at+D,0});
    g[rs(at)+D].push_back({at+D,0});
    build(l,mid,ls(at)); build(mid+1,r,rs(at));
}
void link(int nl,int nr,int u,int w,int opt,int at)
{
    int l=tr[at].l,r=tr[at].r;
    if(nl<=l&&r<=nr)
    {
        if(opt) g[at+D].push_back({u,w});
        else g[u+D].push_back({at,w});
        return;
    }
    int mid=(l+r)>>1;
    if(nl<=mid) link(nl,nr,u,w,opt,ls(at));
    if(nr>mid) link(nl,nr,u,w,opt,rs(at));
    
}
void Dijkstra(int st)
{
    priority_queue<node2> q;
    memset(d,0x3f,sizeof(d));
    d[st]=0; vis=0; q.push({st,0});
    while(!q.empty())
    {
        int u=q.top().u; q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto i : g[u])
        {
            int v=i.v,w=i.w;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                q.push({v,d[v]});
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); read(m); read(s);
    build(1,n,1);
    for(int i=1,op,u,v,l,r,w; i<=m; i++)
    {
        read(op);
        if(op==1)
        {
            read(u); read(v); read(w);
            g[a[u]].push_back({a[v],w});
        }
        else
        {
            read(u); read(l); read(r); read(w);
            link(l,r,a[u],w,op&1,1); // op=2: u->[l,r] , op=3:[l,r]->u;
        }
    }
    for(int i=1; i<=n; i++)
    {
        g[a[i]].push_back({a[i]+D,0}),
        g[a[i]+D].push_back({a[i],0});
    }
    Dijkstra(a[s]+D);
    for(int i=1; i<=n; i++)
        write(d[a[i]]!=INF ? d[a[i]] : -1),pc(" \n"[i==n]);
    return 0;
}

题外话：

Rick and his co-workers have made a new radioactive formula and a lot of bad guys are after them. So Rick wants to give his legacy to Morty before bad guys catch them.

Rick 和他的同事们做出了一种新的带放射性的婴儿食品(???根据图片和原文的确如此...)，与此同时很多坏人正追赶着他们。因此 Rick 想在坏人们捉到他之前把他的遗产留给 Morty。

带放射性的婴儿食品。给我来一碗，~~美汁汁~~！