前排参考lifehappy大佬题解

问题描述

给出你n个点构成的一个有向图，并且存在 m 个边的关系，并且询问从起点 s 去往各个点的最短路长度？
问题规模：
这m个关系中，操作1，直接u连向v一条边权是w的有向边。
操作2，使u连向v，但是这个v是在一个区间中 [l, r]中全部的点，边权等于w
操作3，使u连向v，但是这个u是在一个区间中全部的点，连接边权是w。

Solution

思考最短路径长度就可以使用dijkstra算法，但是直接建图，你会发现这个区间建图非常非常慢非常非常大非常非常多重复的边会出去。
不论时间还是空间都不允许这样建图。那么我们反感的就是区间建图的问题，那么解决区间问题最好的办法不就是线段树吗？
在想如果我们线段树的每个区间节点连接下方节点，最后叶子节点就是留下了应该查询到的点，那么我们只要连接一条边去区间上的父节点，是不是就不用一一连边了。
那么整体思路就处理来了，两颗线段树+dijkstra。
首先给第一颗线段树编号，最底层的叶子节点是我们需要查找到的节点，直接标记 1，2，3... n。
再从上方依次标记n+1,n+2,n+3，等。。这样第一颗线段树构造完成之后，在父节点于左右子节点之间连接一条有向边，但是边权为0。
这样我们构造 u 连向区间 [l,r]中全部的点的时候就可以使用 u 连向线段树1中的 [l,r]区间。
第二棵线段树我们可以这样思考，初始是从叶子节点汇聚到根节点的一颗反向线段树，边权都是0。
随着我们依次构造 区间[l,r] 中的全部节点连接 v ，可以从线段树2中连接一条 [l,r] 去往v的有向边。
这样通过一个起点就可以通过线段树中转找到全部对应的终点了，并且大大减少了边数。大概画图可图下面。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<ll, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 7;

vector<pai> edge[N * 3];
int tot, tree1[N << 2], tree2[N << 2];

#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
int build1(int rt, int l, int r) {
    if (l == r) {
        return tree1[rt] = l;
    }
    tree1[rt] = ++tot;
    int lid = build1(lson);
    int rid = build1(rson);
    edge[tree1[rt]].push_back({ 0, lid });
    edge[tree1[rt]].push_back({ 0, rid });
    return tree1[rt];
}
int build2(int rt, int l, int r) {
    if (l == r) {
        return tree2[rt] = l;
    }
    tree2[rt] = ++tot;
    int lid = build2(lson);
    int rid = build2(rson);
    edge[lid].push_back({ 0, tree2[rt] });
    edge[rid].push_back({ 0, tree2[rt] });
    return tree2[rt];
}

void add1(int rt, int l, int r, int u, int L, int R, int w) {
    if (L <= l and R >= r) {
        edge[u].push_back({ w,tree1[rt] });
        return;
    }
    if (L <= mid)    add1(lson, u, L, R, w);
    if (R > mid)    add1(rson, u, L, R, w);
}

void add2(int rt, int l, int r, int v, int L, int R, int w) {
    if (L <= l and R >= r) {
        edge[tree2[rt]].push_back({ w,v });
        return;
    }
    if (L <= mid)    add2(lson, v, L, R, w);
    if (R > mid)    add2(rson, v, L, R, w);
}

ll dis[N << 3];
bool vis[N << 3];
void dijkstra(int s) {
    ms(dis, 0x3f);
    ms(vis, 0);
    dis[s] = 0;
    priority_queue<pai, vector<pai>, greater<pai>> pq;
    pq.push({ 0,s });
    while (pq.size()) {
        pai now = pq.top();    pq.pop();
        if (vis[now.second])    continue;
        vis[now.second] = 1;
        for (auto& it : edge[now.second]) {
            if (dis[it.second] > dis[now.second] + it.first) {
                dis[it.second] = dis[now.second] + it.first;
                pq.push({ dis[it.second],it.second });
            }
        }
    }
}

int main() {
    int T = 1;
    //T = read();
    while (T--) {
        int n = read(), m = read(), s = read();
        tot = n;
        build1(1, 1, n);
        build2(1, 1, n);
        while (m--) {
            int op = read();
            if (op == 1) {
                int x = read(), y = read(), w = read();
                edge[x].push_back({ w,y });
            }
            else if (op == 2) {
                int x = read(), l = read(), r = read(), w = read();
                add1(1, 1, n, x, l, r, w);
            }
            else {
                int x = read(), l = read(), r = read(), w = read();
                add2(1, 1, n, x, l, r, w);
            }
        }
        dijkstra(s);
        for (int i = 1; i <= n; ++i)
            printf("%lld%c", dis[i] == INF ? -1 : dis[i], " \n"[i == n]);
    }
    return 0;
}