线段树优化建图

三种操作:

• 从 u 到 v 建一条边
• 从 u 到 [l,r] 内的每一个点都建一条边
• 从 [l,r] 内的每一个点都向 v 建一条边

点数,操作数 <= 10^5

显然, O(n^2)的暴力建边会 TLE, 那么怎么优化? 看到区间显然会想到线段树

考虑到一个区间在线段树上最多可以表示成 O(logn) 个节点, 可以考虑建边时直接指向线段树上的节点。

建树

建立两棵线段树:

• 一棵入树负责管理边的终点
• 一棵出树负责管理边的起点

因为两棵树的叶子节点本是同一个节点,因此用边权为0的双向边连接。

入树建树时因从父亲向儿子连边权为0的有向边,出树则应从儿子连向父亲。

算法流程

1. 考虑第二个操作:从 u 到 [l,r] 内的每一个点都建一条边。很显然,应从出树的叶子节点向入树的区间连边。

例:从 6 到 [4,7] 连边,就在线段树区间修改的递归途中边递归边连边

2. 考虑第三个操作:从 [l,r] 内的每一个点都向 v 建一条边。跟操作二一样,应从出树的区间向入树的叶子节点连边。

例:从 4 到 [2,5] 连边。

这样,我们就解决了建图。可以证明，这样连边建出的图和原来的图没有区别。注意，两棵线段树叶子节点之间的边以及从父亲到儿子、从儿子到父亲的边是必不可少的。建图时间复杂度 O(nlogn)。

模板题

CF786B Legacy

建图直接运用上述算法即可。

跑最短路时注意以下几点:

• 需要记录每个原始节点在两棵线段树中分别的位置,以供进行2,3操作
• 进行操作时需要在记录的线段树上的位置上操作
• 连边时注意方向以及叶子节点之间的边、父亲到儿子、儿子到父亲的边,这样跑出来的最短路才是对的

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
int n, m, st, pos_in[N], pos_out[N];
struct Edge {
    int v; ll w;
    bool operator < (const Edge &r) const {
        return r.w < w;
    }
}; vector <Edge> e[N*4*2];
#define lc 2*p
#define rc 2*p+1
#define MID (tr[p].l+tr[p].r)/2
struct Node { int l, r; } tr[N*4*2];
void Build_in(int p, int bL, int bR) { // 建入树
    tr[p].l = bL, tr[p].r = bR;
    if(bL == bR) {
        pos_in[bL] = p;
        // 记录每个叶子节点(相当于图上的节点)在线段树中的下标
        return ;
    }
    int mid = MID;
    Build_in(lc, bL, mid); Build_in(rc, mid + 1, bR);
    // 向孩子连边
    e[p].push_back({lc, 0});
    e[p].push_back({rc, 0});
}
void Build_out(int p, int bL, int bR) { // 建出树
    tr[p].l = bL - n, tr[p].r = bR - n; // 注意下标
    if(bL == bR) { 
        // 向入树的叶子节点连双向边
        e[pos_in[bL-n]].push_back({p, 0});
        e[p].push_back({pos_in[bL-n], 0});
        pos_out[bL-n] = p;
        // 记录每个叶子节点(相当于图上的节点)在线段树中的下标
        return ;
    }
    int mid = MID + n;
    Build_out(lc, bL, mid); Build_out(rc, mid + 1, bR);
    // 孩子向父亲连边
    e[lc].push_back({p, 0});
    e[rc].push_back({p, 0});
}
void Update_in(int p, int qL, int qR, int i, ll d) {
    // 操作二,从出树叶子节点向入树区间连边
    if(qL <= tr[p].l && tr[p].r <= qR) {
        e[i].push_back({p, d});
        return ;
    }
    int mid = MID;
    if(qR <= mid) Update_in(lc, qL, qR, i, d);
    else if(qL > mid) Update_in(rc, qL, qR, i, d);
    else { Update_in(lc, qL, qR, i, d); Update_in(rc, qL, qR, i, d); }
}
void Update_out(int p, int qL, int qR, int i, ll d) {
    // 操作三,从出树区间向入树叶子节点连边
    if(qL <= tr[p].l && tr[p].r <= qR) {
        e[p].push_back({i, d});
        return ;
    }
    int mid = MID;
    if(qR <= mid) Update_out(lc, qL, qR, i, d);
    else if(qL > mid) Update_out(rc, qL, qR, i, d);
    else { Update_out(lc, qL, qR, i, d); Update_out(rc, qL, qR, i, d); }
}
bool vis[N*4*2]; ll dis[N*4*2]; priority_queue <Edge> q;
void dijkstra(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[pos_in[s]] = 0; q.push({pos_in[s], 0});
    // 注意是从线段树中的下标开始
    // 其实pos_in[s]和pos_out[s]有边相连,无所谓从哪个开始
    while(!q.empty()) {
        int u = q.top().v; q.pop();
        if(vis[u]) continue ;
        vis[u] = true;
        for(auto x : e[u]) {
            int v = x.v; ll w = x.w;
            if(dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push({v, dis[v]});
            }
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &st);
    Build_in(2, 1, n); Build_out(3, n + 1, 2 * n);
    // 小细节,两棵线段树根节点分别开在2,3避免混乱
    while(m--) {
        int op; scanf("%d", &op);
        if(op == 1) {
            int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
            e[pos_out[u]].push_back({pos_in[v], w});
        }
        else if(op == 2) {
            int u, l, r; ll w; scanf("%d%d%d%lld", &u, &l, &r, &w);
            Update_in(2, l, r, pos_out[u], w);
            // 注意是从 pos_out 连边
        }
        else {
            int v, l, r; ll w; scanf("%d%d%d%lld", &v, &l, &r, &w);
            Update_out(3, l, r, pos_in[v], w);
            // 注意是连向 pos_in
        }
    }
    dijkstra(st);
    for(int i = 1; i <= n; i++)
        if(dis[pos_in[i]] == 0x3f3f3f3f3f3f3f3f) printf("-1 ");
        else printf("%lld ", dis[pos_in[i]]);
    return 0;
}