D. 杰哥的集合

题解

启发式合并模版题, 每次由小的集合向大的集合合并, 并维护最多的出现次数以及答案。

时间复杂度: $\mathcal{O}(n{}^{2}n)\backslash mathcal\; O(n\; \backslash log^2\; n)$。

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;
}