线段树优化建图

本文最后更新于：星期四, 二月 3日 2022, 9:15 晚上

线段树优化建图

模型

需要多次一个区间向另一个区间连边的建图，求图的一些信息

思路

建立两颗线段树，分别为treeIn,treeOuttreeIn, treeOut表示入边和出边

那么

  • 到了treeIntreeIn的某个节点表示这个点所表示的区间进入
  • 到了treeOuttreeOut的某个节点表示从这个点表示的区间出去

连边：

  • treeIntreeIn父亲节点向儿子节点连权值为00的边，表示进入这个父亲节点的边也可以到儿子节点
  • treeOuttreeOut儿子节点向父亲节点连权值为00的边，表示从这个父亲节点出去的边也可以从儿子也可以走

那么对于每次连边最多连log2nlog_2^n条边

所以有4∗n4*n个点，4∗n+m∗log2n4*n+m*log_2^n条边

模板

CF 786B

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

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
using ll = long long;
using db = double;

const int N = 2e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

struct Edge {
    int v, w;

    Edge() {}
    
    Edge(int v, int w) : v(v), w(w) {}
};

vector<vector<Edge>> G;
int n, q, s, treeIn[N << 2], treeOut[N << 2];
int cnt;
ll dis[N << 2];

void build(int id, int l, int r) {
    if (l == r) {
        treeIn[id] = l;
        treeOut[id] = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    treeIn[id] = ++cnt;
    treeOut[id] = ++cnt;
    G[treeOut[id << 1]].push_back(Edge(treeOut[id], 0));
    G[treeOut[id << 1 | 1]].push_back(Edge(treeOut[id], 0));
    G[treeIn[id]].push_back(Edge(treeIn[id << 1], 0));
    G[treeIn[id]].push_back(Edge(treeIn[id << 1 | 1], 0));
}

void updateIn(int id, int l, int r, int ql, int qr, int from, int cost) {
    if (l >= ql && r <= qr) {
        G[from].push_back(Edge(treeIn[id], cost));
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) updateIn(id << 1, l, mid, ql, qr, from, cost);
    if (qr > mid) updateIn(id << 1 | 1, mid + 1, r, ql, qr, from, cost);
}

void updateOut(int id, int l, int r, int ql, int qr, int to, int cost) {
    if (l >= ql && r <= qr) {
        G[treeOut[id]].push_back(Edge(to, cost));
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) updateOut(id << 1, l, mid, ql, qr, to, cost);
    if (qr > mid) updateOut(id << 1 | 1, mid + 1, r, ql, qr, to, cost);
}

struct node {
    int v, w;

    node() {}
    
    node(int v, int w) : v(v), w(w) {}
    
    bool operator<(const node &other) const {
        return w > other.w;
    }
};

void solve() {
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    priority_queue<node> pq;
    pq.push(node(s, 0));
    while (!pq.empty()) {
        int u = pq.top().v;
        pq.pop();
        for (auto &item: G[u]) {
            if (dis[item.v] > dis[u] + item.w) {
                dis[item.v] = dis[u] + item.w;
                pq.push(node(item.v, dis[item.v]));
            }
        }
    }
}

void RUN() {
    while (scanf("%d %d %d", &n, &q, &s) != EOF) {
        G.clear();
        G.resize(N << 2);
        cnt = n;
        build(1, 1, n);
        for (int _q = 1, op, u, v, l, r, w; _q <= q; ++_q) {
            scanf("%d", &op);
            if (op == 1) {
                scanf("%d %d %d", &u, &v, &w);
                G[u].push_back(Edge(v, w));
            } else if (op == 2) {
                scanf("%d %d %d %d", &u, &l, &r, &w);
                updateIn(1, 1, n, l, r, u, w);
            } else if (op == 3) {
                scanf("%d %d %d %d", &v, &l, &r, &w);
                updateOut(1, 1, n, l, r, v, w);
            } else {
                assert(0);
            }
        }
        solve();
        for (int i = 1; i <= n; ++i) {
            printf("%lld%c", dis[i] == INF ? -1 : dis[i], " \n"[i == n]);
        }
    }
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif

//    ios::sync_with_stdio(false);
//    cin.tie(nullptr), cout.tie(nullptr);

    RUN();

#ifdef LOCAL_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}