DDOSvoid's Blog

2021牛客多校2 L WeChat Walk

发表于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目描述

https://ac.nowcoder.com/acm/contest/11253/L

Solution

很经典的根号分治，首先我们知道朋友总和是 $O(n)$，那么我们按照朋友个数是否大于 $S$ 将点分为大点和小点

对于小点，每次增加可以直接遍历所有朋友

对于大点，首先周围的大点我们可以直接遍历，对于周围的小点，我们维护一个 $mx$ 表示周围小点的最大值，再维护一个 $C$，$C_i$ 表示权值为 $i$ 的小点的个数，关于 $C_i$ 我们只在小点更新的时候将小点 $push$ 进去，这样 $C$ 中的点的个数总共是 $O(nS)$ 的

令大点更新前为 $a$，更新后为 $b$，那么我们只需要拿出 $C_{a+1}$ 到 $C_{b}$ 的中的所有点进行判断即可，注意 $C$ 并不需要删点

取 $S$ 为 $\sqrt n$，总的时间复杂度就是 $O(n\sqrt n)$

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
#include <iostream>
#include <vector>
#include <cmath>
#define maxn 200010
#define maxk 10010
#define maxs 500
#define INF 1000000000
using namespace std;

int n, m, q;

int id[maxn], du[maxn], cnt;

vector<int> A[maxn], B[maxn], C[maxs][maxk];

int a[maxn], champion[maxn], mx[maxn], ans[maxn];
inline void update(int u, int k) {
    ans[u] += champion[u] ? k - champion[u] : 0;
    champion[u] = 0;
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> q; int N = sqrt(2 * m);
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        ++du[x]; ++du[y];
        A[x].push_back(y); A[y].push_back(x);
    }
    for (int u = 1; u <= n; ++u) {
        if (du[u] > N) id[u] = ++cnt;
        for (auto v : A[u])
            if (du[v] > N) B[u].push_back(v);
    }
    for (int i = 1; i <= q; ++i) {
        int u, w; cin >> u >> w; a[u] += w;
        if (du[u] <= N) {
            bool ok = 1; 
            for (auto v : A[u]) {
                if (du[v] > N) mx[v] = max(mx[v], a[u]); 
                if (a[v] > a[u]) ok = 0;
                else ok &= !(a[v] == a[u]), update(v, i); 
            }
            if (ok) {
                for (auto v : B[u]) 
                    C[id[v]][a[u]].push_back(u);
                if (!champion[u]) champion[u] = i;
            } 
        } else {
            bool ok = 1; 
            for (auto v : B[u]) {
                if (a[v] > a[u]) ok = 0;
                else ok &= !(a[v] == a[u]), update(v, i); 
            }
            for (int k = a[u] - w + 1; k <= a[u]; ++k)
                for (auto v : C[id[u]][k])
                    if (a[v] == k) update(v, i); 
            if (ok && mx[u] < a[u] && !champion[u]) champion[u] = i;
        }
    }
    for (int i = 1; i <= n; ++i) if (champion[i]) ans[i] += q - champion[i];
    for (int i = 1; i <= n; ++i) cout << ans[i] << "\n";
    return 0;
}