Codeforces Round #406 (Div. 1)--B. Legacy （线段树优化建图，最短路）

题面：

题意：
给定一张图，求 $S$ 点到其他点的最短路。
图以以下形式给出：
（1） $1$ $x$ $y$ $w$ ，有一条从 $x$ 到 $y$ 的边权为 $w$ 的有向边。
（2） $2$ $x$ $l$ $r$ $w$ ， $x$ 向区间 $[l, r]$ 中的点每个点都连接一条边权为 $w$ 的有向边。
（3） $3$ $y$ $l$ $r$ $w$ ，区间 $[l, r]$ 中的点每个点都向 $x$ 连接一条边权为 $w$ 的有向边。

题解：
直接连边是行不通的，因为这样的时间复杂度和空间复杂度都是 $O (n^{2})$ 的。
涉及区间操作，考虑线段树优化建图。其中线段树上的点动态编号。

建立两棵线段树，一棵 $x - > [l, r]$ 的线段树，一棵 $[l, r] - > x$ 的线段树，其中两棵线段树共用叶子节点表示有一条 $x - > x$ 的边，且权值为 $0$ ，以此把两棵线段树连接起来。

在 $x - > [l, r]$ 的线段树上，初始时父亲向两个儿子连一条权值为 $0$ 的边，表示若 $x$ 点能到达父亲，那么 $x$ 点能到达父亲所表示区间的所有的点。

在 $[l, r] - > x$ 的线段树上，初始时两个儿子向父亲连一条权值为 $0$ 的边，表示若父亲能到达 $x$ 点，那么父亲所表示区间的所有的点均能到达 $x$ 点。

所需空间复杂度分析：
需要 $O (3 n)$ 个点， $O (n * (l o g n + 4))$ 条单向边。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const double alpha=0.75;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int maxp=100100;
const int up=100100;


int head[maxn<<3],ver[maxn<<5],edge[maxn<<5],nt[maxn<<5],tot=1;
ll d[maxn<<3];
bool ha[maxn<<3];

void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z;
    nt[tot]=head[x],head[x]=tot;
}

struct node
{
    int l,r,lc,rc;
}t[maxn<<3];
int rtin,rtout,cnt=0;

int build(int l,int r,bool flag)
{
    if(l==r)
    {
        t[l].l=l,t[l].r=r;
        t[l].lc=t[l].rc=0;
        return l;
    }
    int p=++cnt;
    t[p].l=l,t[p].r=r;
    t[p].lc=build(l,tmid,flag);
    t[p].rc=build(tmid+1,r,flag);
    flag?add(p,t[p].lc,0):add(t[p].lc,p,0);
    flag?add(p,t[p].rc,0):add(t[p].rc,p,0);
    return p;
}

void change(int x,int l,int r,int w,int p,bool flag)
{
    if(l<=t[p].l&&t[p].r<=r)
    {
        flag?add(x,p,w):add(p,x,w);
        return ;
    }
    if(l<=t[t[p].lc].r) change(x,l,r,w,t[p].lc,flag);
    if(r>=t[t[p].rc].l) change(x,l,r,w,t[p].rc,flag);
}

void dij(int s)
{
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    priority_queue<pair<ll,int> >q;
    q.push(pr(0,s));
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(ha[x]) continue;
        ha[x]=true;
        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i],z=edge[i];
            if(d[x]+z<d[y])
            {
                d[y]=d[x]+z;
                q.push(pr(-d[y],y));
            }
        }
    }
}

int main(void)
{
    int n,q,s;
    scanf("%d%d%d",&n,&q,&s);

    cnt=n;
    rtin=build(1,n,true);
    rtout=build(1,n,false);

    int op,x,y,l,r,w;
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&x,&y,&w);
            add(x,y,w);
        }
        else if(op==2)
        {
            scanf("%d%d%d%d",&x,&l,&r,&w);
            change(x,l,r,w,rtin,true);
        }
        else if(op==3)
        {
            scanf("%d%d%d%d",&y,&l,&r,&w);
            change(y,l,r,w,rtout,false);
        }
    }
    dij(s);
    for(int i=1;i<=n;i++)
        printf("%lld ",d[i]==lnf?-1:d[i]);
    putchar('\n');
    return 0;
}