线段树优化建边的速成

坑队友的小白 · 2021-04-03 20:51:34 · 个人记录

前言

这个东西比较简单易懂。

正文

问题引入 \Rightarrow CF786B （PLUS）

现在有一个 n(1 \leq n \leq 10^5) 个节点的有向图，现在给出 m(1 \leq m \leq 10^5) 条信息描述这个图的边，信息有三种：

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。
4. （原题没有）给出五个数 l_1, r_1, l_2, r_2, w，表示 [l_1,r_1] 中所有的点分别向 [l_2,r_2] 中所有的点连一条有向边。

我们需要求出这个图的单源最短路。

基本算法讲解

暴力建图是不可能的。

初始化

将每个点分为入点和出点，一个点 u 被分为 u_{in} 和 u_{out} (学过网络流的\mathrm{dalao}们应该很清楚这是什么意思)，接着，对于所有入点和出点，分别构建一颗线段树维护，我们称之为入树和出树，出树中区间 [l,r] 对应节点的子树中的叶子节点是原图中 [l,r] 的节点的出点，入树同理。对于入树中的非叶子节点，分别向它的左右儿子连一条权值为 0 的有向边，而对于出树中的所有非根节点，向它的父亲节点连一条边权为 0 的边。接着对于所有原图上的点，连接一条出点和入点之间无向边(这是为了防止一些奇怪问题)。

比如 n = 4 的时候，我们构建的线段树和边就是这个样子的：

建图

现在我们需要想办法将原图转化，尽量减少边的数目。

对于出树中某个节点，其表示的区间为 [l_1,r_1]，这个节点有一条有向边连接了入树中的另一个节点，其对应区间为 [l_2, r_2]， 那么可以视为在原图中，满足 \forall~u\in [l_1, r_1], v\in [l_2, r_2], (u,v) \in E。

• 单点 \mathrm{to} 单点：对于一条边 (u,v)，可以直接转化为另一条边 (u_{out}, v_{in}) 。

• 单点 \mathrm{to} 区间：设单点为 u, 区间为 [l,r]。众所周知，一个区间在线段树中会被分成不多于 \log_2 (r-l+1) 个子区间，对于每一个分出的子区间 [l',r'] ，都连接一条从 u_{out} 到这个子区间在入树中的对应节点的有向边。 比如u=4,[l,r] = [1,3] 的时候，可以这样连边：

• 区间 \mathrm{to} 单点：和 单点 \mathrm{to} 区间 类似，不说了。

• 区间 \mathrm{to} 区间：设两个区间为 [l_1, r_1],[l_2, r_2]，边的权值为 w ，应用上面的方法，我们可以对于两个区间的所有子区间分别两两连边，但是这样的边的数量是 O(\log_2^2 n) 的。正确的姿势是构建一个虚点 p，用 区间 \mathrm{to} 单点 的方法，连接 [l_1, r_1] 到 p，这些边的权值是 w，接着用 单点 \mathrm{to} 区间 ，连接 p 到 [l_2, r_2] ，边权都是 0。

尾声

接下来只需要在新图上跑一次单源最短路就好啦，此时源点是原图源点的出点。

Code

PS：这是原题的代码，不是加强之后的代码

const int maxn = 1e5 + 5, maxlg2n = 20;
int n;
struct Edge {
    int v, nex; LL w;
    Edge(int v = 0, LL w = 0, int nex = 0) : v(v), w(w), nex(nex) {}
} E[maxn * maxlg2n << 2];
int hd[maxn << 3], tote;
void addedge(int u, int v, LL w) {
    E[++tote] = Edge(v, w, hd[u]), hd[u] = tote;
}
struct STNode {
    int ls, rs, l, r;
} nd[maxn << 3];
int inid[maxn], outid[maxn], itr_rt, otr_rt, nd_cnt;
void build_tr(int& o, int l, int r, bool fl) {
    o = ++nd_cnt, nd[o].l = l, nd[o].r = r;
    if (l == r) {
        if (fl) inid[l] = o, addedge(o, outid[l], 0), addedge(outid[l], o, 0);
        else outid[l] = o;
        return ;
    }
    int mid = (l + r) >> 1;
    build_tr(nd[o].ls, l, mid, fl);
    build_tr(nd[o].rs, mid + 1, r, fl);
    if (fl) addedge(o, nd[o].ls, 0), addedge(o, nd[o].rs, 0);
    else addedge(nd[o].ls, o, 0), addedge(nd[o].rs, o, 0);
}

void addedge_sig_to_sig(int u, int v, LL w) {
    addedge(outid[u], inid[v], w);
}
void addedge_seq_to_sig(int p, int l, int r, int u, LL w) {
    if (r < nd[p].l || l > nd[p].r) return ;
    if (l <= nd[p].l && nd[p].r <= r) {
        addedge(p, inid[u], w);
        return ;
    }
    addedge_seq_to_sig(nd[p].ls, l, r, u, w);
    addedge_seq_to_sig(nd[p].rs, l, r, u, w);
}
void addedge_sig_to_seq(int p, int u, int l, int r, LL w) {
    if (r < nd[p].l || l > nd[p].r) return ;
    if (l <= nd[p].l && nd[p].r <= r) {
        addedge(outid[u], p, w);
        return ;
    }
    addedge_sig_to_seq(nd[p].ls, u, l, r, w);
    addedge_sig_to_seq(nd[p].rs, u, l, r, w);
}

LL dis[maxn << 3]; int vis[maxn << 3];
priority_queue< pair<LL, int> > pq;
void dij(int src) {
    for (int i = 1; i <= nd_cnt; i++) dis[i] = -1;
    dis[src] = 0, pq.push(make_pair(0, src));
    while (!pq.empty()) {
        int u = pq.top().second; pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = hd[u]; i; i = E[i].nex) {
            int v = E[i].v;
            if (dis[v] == -1 || dis[v] > dis[u] + E[i].w) 
                dis[v] = dis[u] + E[i].w,
                pq.push(make_pair(-dis[v], v));
        }
    } 
}

int main() {
    int q, s;
    scanf("%d%d%d", &n, &q, &s);
    build_tr(otr_rt, 1, n, false), build_tr(itr_rt, 1, n, true);
    for (int i = 1; i <= q; i++) {
        int t, u, v1, v2; LL w;
        scanf("%d", &t);
        if (t == 1) {
            scanf("%d%d%lld", &u, &v1, &w);
            addedge_sig_to_sig(u, v1, w);
        } else if (t == 2) {
            scanf("%d%d%d%lld", &u, &v1, &v2, &w);
            addedge_sig_to_seq(itr_rt, u, v1, v2, w);
        } else {
            scanf("%d%d%d%lld", &u, &v1, &v2, &w);
            addedge_seq_to_sig(otr_rt, v1, v2, u, w);
        }
    }
    dij(outid[s]);
    for (int i = 1; i <= n; i++) printf("%lld ", dis[inid[i]]);
    return 0;
}