#43463. 「计蒜客 2020.2 提高组」保卫水库
Summarize
给定有 $n$ 个节点和 $m$ 条边的有向无环图。每个节点有一定的水量，每个结点的水在水库被破坏后会均等地沿着出边流向其他节点。给出 $k$ 个操作，要求查询某个节点流入的水量，以及修改某个节点的初始水量。
$n\le 5000,m\le 10000,k\le 500000$
测试点的查询和修改次数比例接近 $1:1$
Solution
观察到图为 DAG，并且 $n,n-1..2,1$ 为合法拓扑序。因此可以在图中 $O(n+m)$ 动态规划求出每个城市流入的水量。
由于在某个城市中增加水量之后，流入下游各个城市的比例是固定的。因此可以预处理这些比值。
用一个容器存放所有修改改操作，对于查询，计算容器中所有修改操作对其的影响；当容器大小达到某个值 $s$ 时，执行 $O(n+m)$ 的动态规划下放更新。
复杂度为 $O(sk+\frac{k}{s}(n+m))$，当 $s$ 取 $\sqrt{n+m}$ 时，复杂度取最小值。
Note
均摊复杂度分析 「雅礼集训 2018 Day10」贪玩蓝月 「USACO 2019.12 Platinum」Bessie’s Snow Cow
循环时尽量采用 $n\times(n+m)$ 而不是 $(n+m)\times n$
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const int MAXN = 5005;
ll qpow(ll n, ll k) {
ll ret = 1;
while (k) {
if (k & 1) ret = ret * n % MOD;
n = n * n % MOD;
k >>= 1;
}
return ret;
}
int n, m, k;
int pre[MAXN][MAXN];
int c[MAXN];
ll a[MAXN], b[MAXN], d[MAXN], a1[MAXN];
ll f[MAXN][MAXN];
pair<int, ll> s[MAXN];
int mx = 0, cnt = 0;
void upd() {
for (int u = n; u >= 1; --u) {
b[u] = 0;
for (int i = 1; i <= c[u]; ++i) {
int v = pre[u][i];
b[u] = (b[u] + (a[v] + b[v]) % MOD * d[v] % MOD) % MOD;
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &k);
mx = sqrt(n + m);
for (int i = 1; i <= n; ++i)
scanf("%lld", &a1[i]);
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
if (u > v) {
pre[v][++c[v]] = u;
d[u]++;
} else {
pre[u][++c[u]] = v;
d[v]++;
}
}
for (int i = 1; i <= n; ++i)
d[i] = qpow(d[i], MOD - 2);
for (int u = 1; u <= n; ++u) {
a[u] = 1;
upd();
for (int i = 1; i <= n; ++i)
f[u][i] = b[i];
a[u] = 0;
}
memcpy(a, a1, sizeof(a));
upd();
while (k--) {
int op;
scanf("%d", &op);
if (op == 1) {
int x, y;
scanf("%d%d", &x, &y);
s[++cnt] = make_pair(x, y);
if (cnt == mx) {
for (int i = 1; i <= cnt; ++i)
a[s[i].first] += s[i].second;
cnt = 0;
upd();
}
} else {
int x;
scanf("%d", &x);
ll ans = 0;
for (int i = 1; i <= cnt; ++i)
ans = (ans + f[s[i].first][x] * s[i].second % MOD) % MOD;
printf("%lld\n", (ans + b[x]) % MOD);
}
}
return 0;
}
|