RenaMoe's Blog

念念不忘，必有回响

0%

题解 CF571D Campus

发表于 更新于 分类于 ， Valine：

转化成树上问题 + 树状数组上二分技巧。

题意

题目

维护两类集合 \(A,B\)，初始 \(A_x=B_x=x\)，序列全为 0，有五个操作：

  • 将 \(A_y\) 合并到 \(A_x\)；
  • 将 \(B_y\) 合并到 \(B_x\)；
  • 将集合 \(A_x\) 中元素所在序列的值加上 \(|A_x|\)；
  • 将集合 \(B_x\) 中元素所在序列的值都设为 \(0\)；
  • 求序列下标 \(x\) 的值。

\(n,m\le 10^5\)。

思路

每次把两个集合合并时新建一个虚点作为两者的父亲，操作 \(3\) 就是二叉树上的子树加。

查询单点时就在树上 dfs，用树状数组在时间上维护权值和。

问题在于操作 \(2,4\)，我们需要知道单点询问时，该点最晚的清零操作的时间。

我们用同样的合并方法在第二棵树上处理操作 \(2,4\)，在这棵树上 dfs，用树状数组在时间上维护清零操作。

如果该点有询问操作，那就在树状数组里二分最晚的清零操作：

1
2
3
4
5
6
7
8
9
10
11
// 返回s[i]小于s[x]的最大的i
inline int bound(int x) {
    LL s = query(x);
    x = 0;
    for (int i = 1 << 19; i; i >>= 1) {
        if (x + i < N && sum[x + i] < s) {
            x += i;
            s -= sum[x];
        }
    }
}

这样就可以避免像辣鸡的 RenaMoe 一样在外面套一次二分了，又多个 \(\log\)。

梳理一下，就是先建出两棵树，第二棵树上处理出每个询问点最晚的清零操作，然后在第一棵树上对每个询问点区间查和，复杂度 \(\mathcal O(n\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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
const int N = 1e6 + 9;

struct Ask {
    char opt;
    int x, y;
};
struct BitTree {
    LL sum[N];
    inline void update(int x, LL k) {
        for (int i = x; i < N; i += i & -i) sum[i] += k;
    }
    inline LL query(int x) {
        LL res = 0;
        for (int i = x; i; i -= i & -i) res += sum[i];
        return res;
    }
    inline int bound(int x) {
        LL s = query(x);
        x = 0;
        for (int i = 1 << 19; i; i >>= 1) {
            if (x + i < N && sum[x + i] < s) {
                x += i;
                s -= sum[x];
            }
        }
        return x;
    }
} T;
struct Graph {
    int tot;
    int ls[N], rs[N], fa[N], size[N], id[N];
    inline void init(int n) {
        tot = n;
        for (int i = 1; i <= n * 2; ++i) size[i] = 1, id[i] = i;
    }
    inline void link(int x, int y) {
        ++tot;
        fa[id[x]] = fa[id[y]] = tot;
        ls[tot] = id[x], rs[tot] = id[y];
        size[tot] = size[id[x]] + size[id[y]];
        id[x] = tot;
    }
} G1, G2;

int n, m;
LL ans[N];
Ask q[N];
vector<int> add[N], clr[N], qry[N];

void dfs1(int u) {
    for (int i = 0; i < clr[u].size(); ++i) {
        int j = clr[u][i];
        T.update(j, 1);
    }
    if (u <= n) {
        for (int i = 0; i < qry[u].size(); ++i) {
            int j = qry[u][i];
            q[j].y = T.bound(j);
        }
    }
    else dfs1(G1.ls[u]), dfs1(G1.rs[u]);
    for (int i = 0; i < clr[u].size(); ++i) {
        int j = clr[u][i];
        T.update(j, -1);
    }
}

void dfs2(int u) {
    for (int i = 0; i < add[u].size(); ++i) {
        int j = add[u][i];
        T.update(j, G2.size[u]);
    }
    if (u <= n) {
        for (int i = 0; i < qry[u].size(); ++i) {
            int j = qry[u][i];
            ans[j] = T.query(j) - T.query(q[j].y);
        }
    }
    else dfs2(G2.ls[u]), dfs2(G2.rs[u]);
    for (int i = 0; i < add[u].size(); ++i) {
        int j = add[u][i];
        T.update(j, -G2.size[u]);
    }
}

inline void main() {
    read(n), read(m);
    char str[3];
    for (int i = 1; i <= m; ++i) {
        scanf("%s", str);
        q[i].opt = str[0];
        read(q[i].x);
        if (q[i].opt == 'U' || q[i].opt == 'M') read(q[i].y);
    }
    G1.init(n), G2.init(n);
    for (int i = 1; i <= m; ++i) {
        if (q[i].opt == 'M') {
            G1.link(q[i].x, q[i].y);
        }
        else if (q[i].opt == 'Z') {
            int x = G1.id[q[i].x];
            clr[x].push_back(i);
        }
        else if (q[i].opt == 'U') {
            G2.link(q[i].x, q[i].y);
        }
        else if (q[i].opt == 'A') {
            int x = G2.id[q[i].x];
            add[x].push_back(i);
        }
        else if (q[i].opt == 'Q') {
            qry[q[i].x].push_back(i);
        }
    }
    for (int i = 1; i <= G1.tot; ++i) {
        if (!G1.fa[i]) dfs1(i);
    }
    for (int i = 1; i <= G2.tot; ++i) {
        if (!G2.fa[i]) dfs2(i);
    }
    
    for (int i = 1; i <= m; ++i) {
        if (q[i].opt == 'Q') printf("%lld\n", ans[i]);
    }
}