D. 杰哥的集合
题解
启发式合并模版题, 每次由小的集合向大的集合合并, 并维护最多的出现次数以及答案。
时间复杂度: 。
std:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N];
struct node {
int fa, ans, siz, max_cnt;
map< int, int > mp;
} kk[N];
int find(int x) {
return kk[x].fa == x ? x : kk[x].fa = find(kk[x].fa);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (kk[x].siz > kk[y].siz) swap(x, y);
kk[x].fa = y;
kk[y].siz += kk[x].siz;
for (auto &[i, j] : kk[x].mp) {
int &k = kk[y].mp[i];
k += j;
if (kk[y].max_cnt < k || (kk[y].max_cnt == k && kk[y].ans > i)) {
kk[y].max_cnt = k;
kk[y].ans = i;
}
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m;
map< int, int > mp;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
++ mp[a[i]];
kk[i] = {i, a[i], 1, 1, map< int, int > {pair< int, int >(a[i], 1)}};
}
while (m -- ) {
int op, x, y;
cin >> op >> x;
if (op == 1) {
cin >> y;
merge(x, y);
} else {
cout << kk[find(x)].ans << '\n';
}
}
return 0;
}