P10559 [ICPC2024 Xi'an I] The Last Cumulonimbus Cloud 题解

这种题有一个常见的根号分治做法：设 \(d\) 为度数，显然有 \(O(1)\) 修改单点，\(O(d)\) 查询邻域和 \(O(d)\) 修改邻域，\(O(1)\) 查询单点两种暴力。对度数大于 \(\sqrt n\) 的点使用前者，度数小于等于 \(\sqrt n\) 的点使用后者，可以做到 \(O(m \sqrt n)\) 的时间复杂度。

这种做法的本质让每条边是由度数小的点向度数大的点定向，查询一个点的邻域时将入边集合（提前处理）与出边集合（查询时遍历）的答案相加。因为根号分治的特性，这出边集合的大小不超过 \(O(\sqrt n)\)，于是保证复杂度正确。

本题中考虑类似的定向，由于题目所给的图的特性：每个非空子图都至少有一个点的度数不超过 \(10\)。可以每次选取当前度数最小的点删去，直到把图删空，会得到删除点的顺序，每条边由先删除的点向后删除的点定向，可以保证每个点的出边不超过 \(10\) 条，复杂度正确。

当然，也有一种“启发式定向”的策略（人类智慧）：以 \(p = \dfrac {d_v} {d_u + d_v}\) 为由点 \(u\) 向点 \(v\) 定向的概率，随机数操作一下，就结束了。原理是出边数量一定，我们希望让度数小的节点承担更多的出边，以此得到相对均衡的时间开销。期望复杂度正确，但常数有些大。

既然说到了均衡开销，这篇题解给出了一个美妙的做法：记录每个点被操作的次数，由次数小的向次数大的定向。复杂度非常正确，常数非常小。

这是人类智慧的代码。

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>

using namespace std;

static const int S = 1 << 21;
char buf[S], *p1, *p2;
static inline char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++; }
static inline int read() {
    int x = 0;
    char ch = gc();
    while (!isdigit(ch))
        ch = gc();
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = gc();
    }
    return x;
}

int n, m, q;
int a[300005];
int w[300005];
int deg[300005];
vector<pair<int, int>> edge;
vector<int> vec[300005];

signed main() {
    srand(time(0));
    n = read();
    m = read();
    q = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        ++deg[u], ++deg[v];
        edge.push_back({u, v});
    }
    for (auto [u, v] : edge)
        if ((long long)rand() * (deg[u] + deg[v]) <= (long long)deg[v] * RAND_MAX)
            vec[u].push_back(v);
        else
            vec[v].push_back(u);
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        for (auto v : vec[i])
            w[v] += a[i];
    }
    while (q--) {
        int op = read(), u = read();
        if (op == 1) {
            int x = read();
            a[u] += x;
            for (auto v : vec[u])
                w[v] += x;
        } else {
            int ans = w[u];
            for (auto v : vec[u])
                ans += a[v];
            cout << ans << '\n';
        }
    }
    cout << flush;
    return 0;
}