T3-20 Railway Constr

A90630 Railway Construction 题解

定义与记号

为方便起见，我们先定义：

• dis[u]：节点 1 到节点 u 的最短路长度，称为节点 u 的"距离"。
• 若 dis[u] > dis[v]，称节点 u 比节点 v 更深。
• 若 dis[u] < dis[v]，称节点 u 比节点 v 更浅。
• u -> v：表示从 u 到 v 的一条有向边。
• u --> v：表示从 u 到 v 的一条任意路径。
• 两条路径相交：当且仅当它们经过至少 1 个相同的节点。

---

几个基本事实

1. 新边只能从更浅的点出发：因为所有边权为正，且不能改变任何点的最短路距离，所以对任意节点 u，只能从 dis 严格小于 dis[u] 的节点出发建边。特别地，我们总可以加边 1 -> u，但永远不能加边 u -> 1。
2. 只需考虑最短路 DAG：既然不能改变最短距离，且列车只走最短路，那么原本不在最短路上的边，无论怎么加新边，它都不会出现在任何最短路上。因此我们先跑一遍最短路，只保留最短路上的边，得到的新图是一个 DAG（有向无环图），其拓扑序就是节点距离的升序。后续讨论都在这个 DAG 上进行。
3. 每个非源点至少需要 2 条入边：加完所有新边后，除节点 1 外的每个节点必须有至少 2 条入边。

---

核心引理

引理：如果除节点 1 外每个节点恰好有 2 条入边，则图就满足题意（即对每个 v 存在两条从 1 到 v 的内部点不相交的最短路）。

证明（数学归纳法）：

对任意节点 u，假设所有距离比 u 小的节点都已满足条件，只需证明 u 也满足。设 u 的两条入边分别来自 s 和 t。

情况一：s 或 t 是节点 1。

直接选 1 --> s -> u 和 1 --> t -> u 这两条路径，显然不相交，满足条件。

情况二：s 和 t 都不是节点 1。

• 任取一条路径 1 --> s，称为 path 0。
• 由归纳假设，到 t 存在两条内部不相交的路径 path 1 和 path 2。

如果 path 0 与 path 1（或 path 2）不相交，直接选 path 0 + s -> u 和 path 1 + t -> u 即可。

所以只需处理 path 0 同时与 path 1 和 path 2 都相交 的情况：

• 找到 path 0 与 path 1 或 path 2 相交的最浅节点 a 和最深节点 b。
• 若 a、b 都是 path 0 与 path 1 的交点：选路径 1 -> a -> (沿 path 1) -> b -> s -> u 和 path 2 + t -> u。
• 否则（a 和 b 分别在不同路径上）：选路径 1 -> a -> t -> u 和 1 -> b -> s -> u。

两种情况都满足条件。引理证毕。 ∎

---

算法思路

由引理可知，只需让每个非源点至少有 2 条入边即可。

O(nq) 基础做法

对于固定的 w 数组：

1. 在最短路 DAG 中，找出所有只有 1 条入边的节点，记录其唯一入边的起点。
2. 按距离升序扫描所有节点，维护一个数组 val，记录前面出现过的 w 的最小值和次小值（实际上只需维护下标）。
3. 贪心加边：对每个只有 1 条入边的节点，从前面 w 最小的节点向它连一条新边，代价为该点的 w。

对固定 w 计算一次答案只需 O(n)，所以总复杂度 O(nq)。

O((n+q) log n) 优化

为了加速，我们尝试在 w 变化时动态维护 val 数组。关键技巧是：将所有修改操作反序处理，即只考虑 w 递减的情况。

根据 val 数组的值，可以将序列分成若干子段（subsegment），用 std::set 维护这些子段。每次 w_k 减小时，它会影响 val 的一个后缀，我们找到这个后缀，然后逐段更新 val，直到 w_k 大于当前子段的次小值为止。

对每个子段的更新操作分三类：

1. w_k 恰好是子段的最小值：此操作可能多次发生，但不会改变 val，可以用线段树一次性处理。每次修改至多做 1 次。
2. w_k 恰好是子段的次小值：由于不同子段的次小值互不相同，每次修改也至多做 1 次。
3. w_k 既不是最小值也不是次小值：每执行一次（除第一次外）都会使子段数量减少 1，因此这类操作总共不超过 n + q 次。

用 std::set + 线段树，每个操作可以在 O(log n) 内完成。

---

总复杂度

$$O(m log m + (n + q) log n)$$

其中 $m \log m$ 来自 Dijkstra 建最短路 DAG，$(n+q) log n$ 来自动态维护 val 数组的过程。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>

using std::set;

typedef long long ll;

char BUF_R[1 << 22], *csy1, *csy2;
#define GC (csy1 == csy2 && (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, 1 << 22, stdin), csy1 == csy2) ? EOF : *csy1 ++)

template <class T>
inline void RI(T &t) {
	char c = GC;
	for (t = 0; c < 48 || c > 57; c = GC);
	for (; c > 47 && c < 58; c = GC) t = t * 10 + (c ^ 48);
}

const int MAX_N = 200000 + 5;
const int MAX_M = 600000 + 5;
const int INF32 = 0x7fffffff;
const ll INF64 = 0x3fffffffffffffffll;

int N, M, Q, ques[MAX_N][2];
struct Edge{
    int y, prev, len;
}e[MAX_M];
int elast[MAX_N], ecnt = 1;
std::priority_queue < std::pair <ll, int> > pq;
ll dis[MAX_N], w[MAX_N];
unsigned long long res[MAX_N], ans;
int cnt[MAX_N], fa[MAX_N], a[MAX_N], t;
int rt[MAX_N], pos[MAX_N], sum[MAX_N], endpos[MAX_N];
struct Node{
    int f, s;
    
    Node (int a = 0, int b = 0) : f(a), s(b) {}
    
    inline bool operator == (const Node &comp) const {return f == comp.f && s == comp.s;}
    
    inline void swap() {
        int t = f;
        f = s;
        s = t;
    }
}minv, val[MAX_N];
set <int> s;

namespace SGT{
    const int MAX_M = 10000000;
    
    int tot;
    struct SegmentNode{
        int sum, ls, rs;
    }node[MAX_M];
    
    void segment_modify(int &i, int l, int r, int x) {
        i = i ? i : ++ tot;
        node[i].sum ++;
        if (l == r) return ;
        int mid = (l + r) >> 1;
        mid < x ? segment_modify(node[i].rs, mid + 1, r, x) : segment_modify(node[i].ls, l, mid, x);
    }
    
    int segment_query(int i, int l, int r, int ql, int qr) {
        if (!i) return 0;
        if (l < ql || r > qr) {
            int mid = (l + r) >> 1, res = 0;
            if (mid >= ql) res = segment_query(node[i].ls, l, mid, ql, qr);
            if (mid < qr) res += segment_query(node[i].rs, mid + 1, r, ql, qr);
            return res;
        }else return node[i].sum;
    }
}

int count_illegal(int idx, int l, int r) {
    if (r < l || idx == 1) return 0;
    return SGT::segment_query(rt[idx], 1, N, l, r);
}

int count_legal(int idx, int l, int r) {
    if (r < l) return 0;
    return sum[r] - sum[l - 1] - count_illegal(idx, l, r);
}

void Build(int x, int y, int z) {
    ecnt ++;
    e[ecnt].y = y;
    e[ecnt].len = z;
    e[ecnt].prev = elast[x];
    elast[x] = ecnt;
}

int main() {
    RI(N); RI(M); RI(Q);
    for (int i = 1; i <= N; i ++) {
        RI(w[i]);
        pos[i] = N + 1;
        dis[i] = INF64;
    }
    for (int i = 1; i <= M; i ++) {
        int x, y, z;
        RI(x); RI(y); RI(z);
        Build(x, y, z);
        Build(y, x, z);
    }
    for (int i = 1; i <= Q; i ++) {
        RI(ques[i][0]); RI(ques[i][1]);
        w[ques[i][0]] += ques[i][1];
    }
    
    dis[1] = 0;
    pq.push(std::make_pair(0, 1));
    while (!pq.empty()) {
        int u = pq.top().second;
        ll d = -pq.top().first;
        pq.pop();
        if (dis[u] != d) continue;
        a[++ t] = u;
        for (int i = elast[u]; i; i = e[i].prev) {
            int v = e[i].y;
            if (d + e[i].len < dis[v]) {
                dis[v] = d + e[i].len;
                pq.push(std::make_pair(-dis[v], v));
            }
        }
    }
    for (int i = 2; i <= ecnt; i ++) {
        int u = e[i ^ 1].y, v = e[i].y;
        if (dis[u] + e[i].len == dis[v]) {
            cnt[v] ++; fa[v] = u;
        }
    }
    
    ans = 0;
    s.insert(1);
    pos[1] = 1;
    minv.f = 1;
    minv.s = N + 1;
    val[1] = minv;
    w[N + 1] = INF64;
    for (int i = 2, j = 2; i <= N; i ++) {
        int u = a[i];
		for (; dis[a[j]] < dis[u]; j ++) {
		    int v = a[j];
		    pos[v] = i;
    		if (w[v] < w[minv.f]) {
    		    s.insert(i);
    		    endpos[minv.f] = i;
    		    minv.s = minv.f;
    		    minv.f = v;
    		    val[i] = minv;
    		}else if (w[v] < w[minv.s]) {
    		    s.insert(i);
    		    minv.s = v;
    		    val[i] = minv;
    		}
    	}
    	sum[i] = sum[i - 1];
        if (cnt[u] < 2) {
            sum[i] ++;
            if (fa[u] > 1) SGT::segment_modify(rt[fa[u]], 1, N, i);
		    ans += w[(minv.f == 1 || minv.f != fa[u]) ? minv.f : minv.s];
		}
    }
    endpos[minv.f] = N + 1;
    s.insert(N + 1);
    res[Q] = ans;
    
    for (int i = Q; i > 0; i --) {
        int k = ques[i][0], x = ques[i][1];
        w[k] -= x;
        if (pos[k] > N) {
            res[i - 1] = ans;
            continue;
        }
        set <int>::iterator it = -- s.upper_bound(pos[k]), lst;
        minv = Node();
        int response = 0, p = pos[k];
        if (k == val[*it].f) response = 1;
        else if (k == val[*it].s) response = 2;
        while (response >= 0 && *it <= N) {
            lst = it ++;
            if (response == 0) {
                if (w[val[*lst].s] <= w[k]) break;
                if (w[k] < w[val[*lst].f]) {
                    if (!minv.f) endpos[val[*lst].f] = p;
                    int c = count_illegal(val[*lst].f, p, (*it) - 1), tot = sum[(*it) - 1] - sum[p - 1];
                    ans -= 1ull * c * w[val[*lst].s] + 1ll * (tot - c) * w[val[*lst].f];
                    if (p != *lst) val[p] = val[*lst];
                    val[p].s = val[p].f;
                    val[p].f = k;
                    c = count_illegal(k, p, (*it) - 1);
                    ans += 1ull * c * w[val[p].s] + 1ll * (tot - c) * w[k];
                    if (p != *lst) {
                        s.insert(p);
                        minv = val[p];
                    }else if (minv == val[p]) s.erase(lst);
                    else minv = val[p];
                    endpos[k] = p = *it;
                }else {
                    ans += 1ull * count_illegal(val[*lst].f, p, (*it) - 1) * (w[k] - w[val[*lst].s]);
                    if (p != *lst) val[p] = val[*lst];
                    val[p].s = k;
                    if (p != *lst) {
                        s.insert(p);
                        minv = val[p];
                    }else if (minv == val[p]) s.erase(lst);
                    else minv = val[p];
                    p = *it;
                }
            }else if (response == 1) {
                it = s.lower_bound(endpos[k]);
                ans -= 1ull * count_legal(k, p, (*it) - 1) * x;
                p = *it; lst = it; lst --;
                minv = val[*lst];
                response = val[p].s == k ? 2 : 0;
            }else {
                if (w[val[*lst].f] <= w[k]) {
                    ans -= 1ull * count_illegal(val[*lst].f, p, (*it) - 1) * x;
                    minv = val[*lst]; p = *it;
                }else {
                    endpos[val[*lst].f] = p;
                    int c = count_illegal(val[*lst].f, p, (*it) - 1), tot = sum[(*it) - 1] - sum[p - 1];
                    ans -= 1ull * c * (w[val[*lst].s] + x) + 1ull * (tot - c) * w[val[*lst].f];
                    if (p != *lst) val[p] = val[*lst];
                    val[p].swap();
                    c = count_illegal(val[p].f, p, (*it) - 1);
                    ans += 1ull * c * w[val[p].s] + 1ull * (tot - c) * w[val[p].f];
                    if (p != *lst) {
                        s.insert(p);
                        minv = val[p];
                    }else if (minv == val[p]) s.erase(lst);
                    else minv = val[p];
                    endpos[k] = p = *it;
                }
                response = 0;
            }
        }
        res[i - 1] = ans;
    }
    
    for (int i = 0; i <= Q; i ++) printf("%llu\n", res[i]);
    
    return 0;
}