DDOSvoid's Blog

hdu 6756 Finding a MEX

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

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=6756

简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，每个点有点权 $a_i$，现在有 $q$ 个操作，操作有两种，第一种操作给定 $x$ 和 $y$，修改 $a_x=y$；第二种操作给定 $x$，求与 $x$ 有连边的所有点 $a_y$ 所形成的的集合 $S$ 的 $mex$ 是多少

$n,m,q\le 10^5$

Solution

因为所有点的总点数为 $2n$，所以我们按照点的度数进行根号分治，以 $B$ 为分界线，度数小于等于 $B$ 的称为小点，度数大于 $B$ 的称为大点

对于小点的查询，我们直接暴力即可，时间复杂度为 $O(B)$

对于大点的查询，我们对每个大点维护一个树状数组，查询 $mex$ 可以在树状数组上二分，同时修改一个点的点权我们只需要修改这个点周围所有大点的树状数组即可，注意到一个点周围最多只有 $\frac{n}{B}$ 个大点，所有这一部分的时间复杂度为 $O(\frac{n}{B}\log n)$

总时间复杂度为 $O(B+\frac{n}{B}\log 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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <cmath>
#include <vector>
#define maxn 100010
#define lowbit(i) ((i) & (-i))
using namespace std;

int n, m, q, a[maxn], Block;
vector<int> G[maxn], H[maxn];

int Log[maxn];
struct Fenwick {
    int *Bit, *cnt, n;

    void init(int _n) {
        static int B[maxn * 20], C[maxn * 20], *curB = B, *curC = C;
        n = _n; Bit = curB; cnt = curC; curB += n + 1; curC += n + 1; 
        for (int i = 1; i <= n; ++i) Bit[i] = cnt[i] = 0;
    }
    void ins(int i, int v) {
        i = min(i + 1, n); 
        if (cnt[i] == 0 && v > 0 || cnt[i] == 1 && v < 0) add(i, v);
        cnt[i] += v;
    }
    void add(int i, int v) { while (i <= n) Bit[i] += v, i += lowbit(i); }
    int query() {
        int l = 0, r = n + 1, mid, sum = 0, ans = 0; 
        while (l + 1 < r) {
            mid = l + Log[r - l];
            if (sum + Bit[mid] < mid) r = mid;
            else sum += Bit[mid], ans = l = mid;
        } return ans;
    }
} B[maxn];

inline void solve_1() {
    int u, x; cin >> u >> x; 
    for (auto v : H[u]) {
        B[v].ins(a[u], -1);
        B[v].ins(x, 1); 
    } a[u] = x; 
}

bool vis[maxn];
inline void solve_2() {
    int x; cin >> x;
    if (G[x].size() <= Block) {
        for (int i = 0; i <= Block; ++i) vis[i] = 0; 
        for (auto y : G[x]) vis[a[y]] = 1;
        int ans = 0; while (vis[ans]) ++ans;
        cout << ans << "\n";
    } else cout << B[x].query() << "\n";
}

void work() {
    cin >> n >> m; Block = sqrt(n); 
    for (int i = 1; i <= n; ++i) G[i].clear(), H[i].clear();
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        G[x].push_back(y); G[y].push_back(x);
    }
    for (int u = 1; u <= n; ++u) {
        if (G[u].size() <= Block) continue; 
        B[u].init(G[u].size() + 1);
        for (auto v : G[u]) B[u].ins(a[v], 1), H[v].push_back(u);
    } cin >> q; 
    for (int i = 1; i <= q; ++i) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else solve_2();
    }
}
 
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    Log[1] = 0; Log[2] = 1;
    for (int i = 3; i <= 100000; ++i) Log[i] = i > 2 * Log[i - 1] ? Log[i - 1] * 2 : Log[i - 1];
    
    int T; cin >> T; 
    while (T--) work(); 
    return 0; 
}