今天vp遇到两道启发式合并题，觉得很有意思然后记录一下qwq
最近感觉和队友在一起a题的时候很开心O.o，但是这种日子也不长了
F. Strange Memory
题目链接：Problem - F - Codeforces
题目描述
给出一颗带点权、根节点为1的树，求出 $\sum_{i=1}^{n}\sum_{j=i+1}^{n}[a_i \oplus a_j = a_{lca(i,j)}](i \oplus j)$。
$ \oplus$ 代表异或，也就是求出两节点权值满足 $a_i \oplus a_j = a_{lca(i,j)}$ 时， $i \oplus j$ 的和。
思路
首先看到题目第一眼想到的就是 dsu on tree，扫描每颗子树的根节点 $u$，然后枚举子树内的节点 $v$ ，保存 $a_u \oplus a_v$ 然后再枚举子树内的节点，然后计数。
后来发现贡献其实是由根节点的所有儿子所属的子树相互产生的。所以我们必须枚举儿子的子树，想到根节点是不断变化的，保存 $a_u \oplus a_v$ 有些许困难，所以换一种思路，我们保存 $a_v$， 然后枚举时再由 $a_v \oplus a_u$ 来计数。
这道题前前后后花了快两个小时，之前学的都忘干净了555，不过好在最后ac了…
代码
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
| #include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;
int n, a[N];
vector< int > adj[N];
int siz[N], son[N], dfn[N], idx[N];
int num[M][18][2];
void dfs1(int x, int p) {
siz[x] = 1;
dfn[x] = ++ dfn[0];
idx[dfn[0]] = x;
for (auto &y : adj[x]) {
if (y ^ p) {
dfs1(y, x);
siz[x] += siz[y];
if (siz[y] > siz[son[x]]) {
son[x] = y;
}
}
}
}
long long ans = 0;
void dfs2(int x, int p, bool keep) {
for (auto &y : adj[x]) {
if (y != son[x] && y != p) {
dfs2(y, x, false);
}
}
if (son[x]) {
dfs2(son[x], x, true);
}
for (auto &y:adj[x]) {
if (y != son[x] && y != p) {
for (int i = dfn[y]; i <= dfn[y] + siz[y] - 1; ++i) {
int v = idx[i];
if ((a[v] ^ a[x]) <= 1000000) {
for (int j = 0; j < 18; ++j) {
ans += (1LL << j) * num[a[v] ^ a[x]][j][!(v >> j & 1)];
}
}
}
for (int i = dfn[y]; i <= dfn[y] + siz[y] - 1; ++i) {
int v = idx[i];
for (int j = 0; j < 18; ++j) {
++ num[a[v]][j][v >> j & 1];
}
}
}
}
for (int j = 0; j < 18; ++j) {
++ num[a[x]][j][x >> j & 1];
}
if (!keep) {
for (int i = dfn[x]; i <= dfn[x] + siz[x] - 1; ++i) {
int v = idx[i];
for (int j = 0; j < 18; ++j) {
--num[a[v]][j][v >> j & 1];
}
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) {
scanf("%d", &a[i]);
}
for (int i = 1; i < n; ++ i) {
int u, v;
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs1(1, 0);
dfs2(1, 0, true);
printf("%lld\n", ans);
return 0;
}
|
K. Ragdoll
题目链接：Problem - K - Codeforces
题目描述
刚开始有 $n$ 个空集合，有 $m$ 次操作，每次操作如下：
- 新建一个集合，向其中插入一个权值为 $v$ 的节点 $x$
- 合并 $x$ 与 $y$ 所属的集合，若已在同一集合则不操作
- 修改节点 $x$ 的权值为 $v$
每次操作后，都需要输出所有集合内 $\gcd \left(a_i,a_j\right)=a_i \oplus a_j$ 的个数和
思路
这题思维难度相对前一题较简单，我们只需要动态地维护所有集合内的数的个数即可。
思考 $\gcd \left(a_i,a_j\right)=a_i \oplus a_j$ 这个公式，通过打表观察到每个 $a_i$ 满足条件的 $a_j$ 个数并不多，最多只有72个，所以我们直接存储每个数满足条件的数。
每次合并时我们暴力遍历两个集合中 $size$ 相对小的集合，然后计数。
修改操作很简单，就不讲解了。
代码
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
| #include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, M = 2e5 + 5;
vector< int > g[M];
vector< int > gg[M];
void init(){
for(int i = 1;i< M; ++ i){
for(int j = i;j < M; j += i){
g[j].push_back(i);
}
}
for(int i = 1;i < M; ++ i){
for(auto x : g[i]){
int b = x ^ i;
if (b < M) {
if(gcd(b,i) == x){
gg[i].push_back(b);
}
}
}
}
}
int f[N], n, m;
int a[N];
long long ans;
unordered_map< int, int > tree[N];
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return;
}
if (tree[x].size() > tree[y].size()) {
swap(x, y);
}
for (auto &[u, cnt] : tree[x]) {
for (auto &v:gg[u]){
if(tree[y].find(v)!=tree[y].end())
ans += tree[y][v] * cnt;
}
}
for (auto &[u, cnt] : tree[x]) {
tree[y][u] += cnt;
}
f[x] = y;
tree[x].clear();
}
void change(int x, int v) {
int y = find(x);
for (auto &v : gg[a[x]]) {
ans -= tree[y][v];
}
tree[y][a[x]] --;
++ tree[y][v];
a[x] = v;
for (auto &v : gg[a[x]]) {
ans += tree[y][v];
}
}
int main() {
init();
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++ i) {
scanf("%d",&a[i]);
++ tree[i][a[i]];
}
iota(f + 1, f + n + m + 1, 1);
while (m -- ) {
int x, y, op;
scanf("%d %d %d", &op, &x, &y);
if (op == 1) {
a[x] = y;
++ tree[x][y];
} else if (op == 2) {
merge(x, y);
} else {
change(x, y);
}
printf("%lld\n",ans);
}
return 0;
}
|
