Legacy（线段树建图，最短路）

题目：

给 $n$ 个点。 $m$ 个操作。
$[1\space u\space v\space w]$ ： $u$ 和 $v$ 建权值 $w$ 的有向边；
$[2\space u\space l\space r\space w]$ ： $u$ 和 $v∈[l,r]$ 建权值 $w$ 的有向边；
$[3\space v\space l\space r\space w]$ ： $u∈[l,r]$ 和 $v$ 建权值 $w$ 的有向边；
问从 $s$ 点到其他点的最短路。无法到达输出 $-1$ 。
$n、q≤1e5$

做法：

直接建图时间、空间复杂度都太大了。我们需要用线段树维护区间建图。开两棵线段树 $T1、T2$ ， $T1$ 自底向上建零边， $T2$ 自顶向下建零边。如下图：
图片说明
当我们处理 $[2\space u\space l\space r\space w]$ 这种情况时，只需用 $u$ 和 $T2$ 线段树中的某些段点建边。处理 $[3\space v\space l\space r\space w]$ 时，就是 $T1$ 线段树中某些段点和 $v$ 建边。至于 $[1\space u\space v\space w]$ 直接建边。这样大大减少了边数。建完图后 $dijkstra$ 跑单源最短路。

代码：

#include <bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
inline int read(void){
    char ch = getchar(); int ans = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) ans = ans*10 + ch-'0', ch = getchar();
    return ans;
}
const int N = 1e5 + 7;
const int M = 2e6 + 7;
const ll inf = 1e17;
int n, m, s, tag, T1[N<<2], T2[N<<2];
struct edge{
    int v, w, nxt;
}e[M];
int tot, head[N*10];
ll dis[N*10];
priority_queue<pair<ll,int> > q;
void addedge(int u, int v, int w){
    e[tot] = (edge){v, w, head[u]}; head[u] = tot++;
}
int build1(int l, int r, int rt){
    if (l == r){
        return T1[rt] = l;
    }
    T1[rt] = ++tag;
    int mid = (l+r) >> 1;
    int lid = build1(l, mid, lson); 
    int rid = build1(mid+1, r, rson);
    addedge(lid, T1[rt], 0);
    addedge(rid, T1[rt], 0);
    return T1[rt];
}
int build2(int l, int r, int rt){
    if (l == r){
        return T2[rt] = l;
    }
    T2[rt] = ++tag;
    int mid = (l+r) >> 1;
    int lid = build2(l, mid, lson); 
    int rid = build2(mid+1, r, rson);
    addedge(T2[rt], lid, 0);
    addedge(T2[rt], rid, 0);
    return T2[rt];
}
void upd_edge1(int v, int w, int L, int R, int l, int r, int rt){
    if (L <= l && r <= R){
        addedge(T1[rt], v, w); return;
    }
    int mid = (l+r) >> 1;
    if (L <= mid) upd_edge1(v, w, L, R, l, mid, lson);
    if (R > mid) upd_edge1(v, w, L, R, mid+1, r, rson);
}
void upd_edge2(int u, int w, int L, int R, int l, int r, int rt){
    if (L <= l && r <= R){
        addedge(u, T2[rt], w); return;
    }
    int mid = (l+r) >> 1;
    if (L <= mid) upd_edge2(u, w, L, R, l, mid, lson);
    if (R > mid) upd_edge2(u, w, L, R, mid+1, r, rson);
}
void init(void){
    tot = 0; memset(head, -1, sizeof head);
    tag = n;
    build1(1, n, 1); build2(1, n, 1);
}
void dijkstra(int s){
    fill(dis, dis+tag+1, inf);
    dis[s] = 0; q.push(make_pair(0, s));
    while (!q.empty()){
        int u = q.top().second;
        ll d = -q.top().first; q.pop();
        if (d != dis[u]) continue;
        for (int i = head[u]; i != -1; i = e[i].nxt){
            int v = e[i].v, w = e[i].w;
            if (dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}
int main(void){
    n = read(), m = read(), s = read();
    init();
    for (int i = 1; i <= m; ++i){
        int op, u, v, w, l, r;
        op = read();
        if (op == 1){
            u = read(), v = read(), w = read();
            addedge(u, v, w);
        }else if (op == 2){
            u = read(), l = read(), r = read(), w = read();
            upd_edge2(u, w, l, r, 1, n, 1);
        }else{
            v = read(), l = read(), r = read(), w = read();
            upd_edge1(v, w, l, r, 1, n, 1);
        }
    }
    dijkstra(s);
    for (int i = 1; i <= n; ++i){
        printf("%lld ", (dis[i] == inf ? -1 : dis[i]));
    }
    printf("\n");
    return 0;
}