CF786B Legacy

Link

Sol

这是一道线段树优化连边板子题

要用这个的题通常是这样的, 一个点往一个区间内所有点连边,或者一个区间都往一个点连边. 如果你直接暴力连的话时间很差劲,你就需要线段树优化连边.

思路大概是这样的,运用线段树的思想. 线段树的每一个叶子节点对应原图的节点, 非叶节点就对应的是一段区间的点. 这样一来连边就只需要连接线段树上的点.

比如说一个题往一个区间内所有点连边,就是从线段树的叶节点往一个代表整个区间的点连边.这样相当于是从线段树深度比较深的底部往浅的地方连. 一个区间都往一个点连就是往下连. 每次都按照递归在线段树上找一下对应区间的节点,然后连就可以了.

实现的话都可以, 这道题这两种连边都有. 就直接开两个动态开点线段树, 然后共用叶子节点

Code

不懂的问题看了代码就懂了

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 4e5 + 5;
const int inf = 1e18;

int n, q, s, root1, root2, nodeCnt, num;
int head[SIZE], dis[SIZE], vis[SIZE], lson[SIZE], rson[SIZE];

struct edge {
    int to, v, nxt;
} edge[SIZE * 10];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline void addEdge(int u, int v, int d) {
    edge[++ num].to = v, edge[num].v = d, edge[num].nxt = head[u];
    head[u] = num;
}

inline int buildDown(int l, int r) {
    if (l == r) return l;
    int mid = (l + r) >> 1, p = ++ nodeCnt;
    lson[p] = buildDown(l, mid); rson[p] = buildDown(mid + 1, r);
    addEdge(p, lson[p], 0); addEdge(p, rson[p], 0);
    return p;
}

inline int buildUp(int l, int r) {
    if (l == r) return l;
    int mid = (l + r) >> 1, p = ++ nodeCnt;
    lson[p] = buildUp(l, mid); rson[p] = buildUp(mid + 1, r);
    addEdge(lson[p], p, 0); addEdge(rson[p], p, 0);
    return p;
}

inline void link(int from, int to, int val, int l, int r, int L, int R, int typ) {
    if (L <= l && r <= R) {
        if (typ == 1) addEdge(from, to, val); // up -> down
        else addEdge(to, from, val); // down -> up
        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) link(lson[from], to, val, l, mid, L, R, typ);
    if (R > mid) link(rson[from], to, val, mid + 1, r, L, R, typ);
}

inline void dijkstra() {
    std::priority_queue < pair < int, int > > q;
    for (int i = 1; i <= nodeCnt; ++ i) dis[i] = inf;
    memset(vis, 0, sizeof(vis));
    q.push(make_pair(0, s)); dis[s] = 0;
    while (!q.empty()) {
        int u = q.top().second, v;
        q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (int i = head[u]; i; i = edge[i].nxt) {
            v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].v) {
                dis[v] = dis[u] + edge[i].v;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}

signed main() {
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    nodeCnt = n = read(), q = read(), s = read(); root1 = nodeCnt + 1;
    buildDown(1, n); root2 = nodeCnt + 1;
    buildUp(1, n);
    int opt, v, u, l, r, w;
    while (q --) {
        opt = read();
        if (opt == 1) {
            u = read(), v = read(), w = read();
            addEdge(u, v, w);
        }
        else {
            u = read(), l = read(), r = read(), w = read();
            link(opt ^ 3 ? root1 : root2, u, w, 1, n, l, r, opt - 2);
        }
    }
    dijkstra();
    for (int i = 1; i <= n; ++ i) printf("%lld ", dis[i] == inf ? -1 : dis[i]);
    return 0;
}