Codeforces - 786B Legacy 线段树建图+最短路

传送门：https://codeforces.com/contest/786/problem/B

题意

有n个星球，q条路径，问从一个起点为s的星球到其他星球的距离。

每条路径可能有以下三种形式：

  • $1\;u\;v\;w$：一个点u到另一点v，路程为w
  • $2\;u\;l\;r\;w$：从一点u到[l,r]区间任意一个星球，路程为w
  • $3\;u\;l\;r\;w$：从[l,r]区间任意一个星球到另一点u，路程为w

思路

最短路问题，直接Dijkatra跑出来。不过这题考查的点是区间和点怎么建边。区间？线段树！！！

因为线段树里的一个点能代表一个区间，所以我们可以利用线段树建图。

因为有的操作是点连接区间，有的是区间连接点，所以一棵线段树是不够的，需要两棵线段树-一棵入树、一棵出树。

对于入树，我们认为他是区间连接点的线段树，所以叶子结点都要往父节点走，如图所示。

对于出树，我们认为他是点连接区间的线段树，所以父节点要往叶子结点走，如图所示。

这两棵线段树内部的边在建树的时候就建边，并且认为不需要路程。 而两棵树的叶子结点没有连，虽方便起见，我们可以整合成一幅图，如图所示：

我们默认边都是从下指向上的（统一）。 这样就方便我们的三个操作： 如果是点与点建边，将入树的叶子结点与出树的叶子结点相连。 如果是点与区间建边，将入树的叶子结点与出树的区间结点相连。 如果是区间与点建边，将入树的区间结点与入树的叶子结点相连。

最后跑一遍最短路即可。

Code(374MS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
##include "bits/stdc++.h"
using namespace std;

typedef long long ll;

const ll INF = 1e18;

const int maxn = 2e5 + 10;
const int N = 2e5 + 10;

struct Edge {
    int v, next;
    ll w;
}e[maxn << 4];
int head[maxn << 4], cnt;

inline void add(int u, int v, ll w) {
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}

int idin[maxn << 4], idout[maxn << 4]; // 入树和出树上点的编号

##define lc u << 1
##define rc u << 1  1

struct Tree {
    int l, r, id;
}tin[N << 4], tout[N << 4];

int tot; // 动态开点内存池

void push_up_in(int u) { // 叶子结点向父节点连线
    add(tin[lc].id, tin[u].id, 0);
    add(tin[rc].id, tin[u].id, 0);
}

void push_up_out(int u) { // 父节点向叶子结点连线
    add(tout[u].id, tout[lc].id, 0);
    add(tout[u].id, tout[rc].id, 0);
}

// 入树
void build_in(int u, int l, int r) {
    tin[u].l = l; tin[u].r = r;
    tin[u].id = ++tot;
    if(l == r) {
        idin[l] = tin[u].id;
        return ;
    }
    int m = (l + r) >> 1;
    build_in(lc, l, m);
    build_in(rc, m + 1, r);
    push_up_in(u);
}

// 出树
void build_out(int u, int l, int r) {
    tout[u].l = l; tout[u].r = r;
    tout[u].id = ++tot;
    if(l == r) {
        idout[l] = tout[u].id;
        add(idout[l], idin[l], 0); // 两棵树的叶子结点以0距离连接
        return ;
    }
    int m = (l + r) >> 1;
    build_out(lc, l, m);
    build_out(rc, m + 1, r);
    push_up_out(u);
}

void modify_in(int u, int ql, int qr, int v, ll w) { // 点连接区间
    if(ql <= tout[u].l && tout[u].r <= qr) {
        add(idin[v], tout[u].id, w);
        return ;
    }
    int mid = (tout[u].l + tout[u].r) / 2;
    if(ql <= mid) modify_in(lc, ql, qr, v, w);
    if(qr > mid)  modify_in(rc, ql, qr, v, w);
}

void modify_out(int u, int ql, int qr, int v, ll w) { // 区间连接点
    if(ql <= tin[u].l && tin[u].r <= qr) {
        add(tin[u].id, idout[v], w);
        return ;
    }
    int mid = (tin[u].l + tin[u].r) / 2;
    if(ql <= mid) modify_out(lc, ql, qr, v, w);
    if(qr > mid)  modify_out(rc, ql, qr, v, w);
}

bool vis[maxn << 4];
ll dis[maxn << 4];

struct node {
    int now;
    ll d;
    bool operator < (const node &rhs) const {
        return d > rhs.d;
    }
};

priority_queue<node> q;

void Dij(int s) {
    dis[s] = 0;
    q.push({s, 0});
    while(!q.empty()) {
        node p = q.top();
        q.pop();
        int u = p.now;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if(dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                q.push({v, dis[v]});
            }
        }
    }
}

void solve() {
    int n, m, s; cin >> n >> m >> s;
    build_in(1, 1, n);
    build_out(1, 1, n);
    for(int i = 1;i <= m; i++) {
        int opt, l, r, u, v;
        ll w;
        cin >> opt;
        // 规定连接都是由下往上，入树的点连接出树的点
        if(opt == 1) {
            cin >> u >> v >> w;
            add(idin[u], idout[v], w);
        }
        else if(opt == 2) { // 点连接区间
            cin >> u >> l >> r >> w;
            modify_in(1, l, r, u, w);
        }
        else if(opt == 3) { // 区间连接点
            cin >> u >> l >> r >> w;
            modify_out(1, l, r, u, w);
        }
    }
    // 预处理所有点，线段树的叶子结点编号会超过n，，所以要多开几倍
    for(int i = 1;i <= 8 * n; i++) dis[i] = INF;
    Dij(idin[s]);
    for(int i = 1;i <= n; i++) {
        if(dis[idin[i]] != INF) cout << dis[idin[i]] << " ";
        else cout << -1 << " ";
    }
    cout << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/01/13/codeforces-786b/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！