P8496 [NOI2022] 众数 题解

· · 题解

最近 7 年最水的 D1T1。

可能是不太一样的做法。

用权值线段树维护每个数出现的次数，链表维护序列。

操作 4 即合并两棵权值线段树、两个链表，操作 2 就是删除链表尾的元素并在权值线段树上修改。

显然，如果一个序列存在绝对众数，那么它必然等于这个序列的中位数。所以操作 3 就是询问 k 个序列整体的中位数，并检查这个数的出现次数。

考虑二分中位数，在 k 棵线段树上分别查询前缀和，再判断出现次数，然而时间复杂度是 O(n \log^2 n)，可能无法通过。把二分中位数改成在 k 棵线段树上二分即可做到 O(n \log n)。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e6 + 3;
const int SIZE = N * 21;

int n, q, m;
int a[N], siz[N], head[N], tail[N], pre[N];

inline void insert(int i, int p) {
    pre[p] = tail[i];
    tail[i] = p;
    if (!siz[i]) head[i] = p;
    ++siz[i];
}

inline void erase(int i) {
    tail[i] = pre[tail[i]];
    --siz[i];
    if (!siz[i]) head[i] = 0;
}

inline void link(int i, int j, int k) {
    head[k] = siz[i] ? head[i] : head[j];
    tail[k] = siz[j] ? tail[j] : tail[i];
    siz[k] = siz[i] + siz[j];
    if (head[j]) pre[head[j]] = tail[i];
}

int rt[N], ls[SIZE], rs[SIZE], tot;
ll cnt[SIZE];

void update(int &x, int k, int v, int l = 1, int r = n + q) {
    if (!x) x = ++tot;
    cnt[x] += v;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (k <= mid) update(ls[x], k, v, l, mid);
    else update(rs[x], k, v, mid + 1, r);
}

void merge(int &x, int &y, int l = 1, int r = n + q) {
    if (!x || !y) {
        x += y;
        return;
    }
    cnt[x] += cnt[y];
    if (l == r) return;
    int mid = (l + r) >> 1;
    merge(ls[x], ls[y], l, mid);
    merge(rs[x], rs[y], mid + 1, r);
}

ll query(int x, int k, int l = 1, int r = n + q) {
    if (!x) return 0;
    if (l == r) return cnt[x];
    int mid = (l + r) >> 1;
    if (k <= mid) return query(ls[x], k, l, mid);
    return query(rs[x], k, mid + 1, r);
}

int c[N], tmp[N], len;

int search(ll k, int l = 1, int r = n + q) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    ll sum = 0;
    for (int i = 1; i <= len; ++i)
        sum += cnt[ls[tmp[i]]];
    if (sum >= k) {
        for (int i = 1; i <= len; ++i)
            tmp[i] = ls[tmp[i]];
        return search(k, l, mid);
    } else {
        for (int i = 1; i <= len; ++i)
            tmp[i] = rs[tmp[i]];
        return search(k - sum, mid + 1, r);
    }
}

int main() {
    freopen("major.in", "r", stdin);
    freopen("major.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        int sz;
        cin >> sz;
        for (int j = 1; j <= sz; ++j) {
            int x;
            cin >> x;
            a[++m] = x;
            insert(i, m);
            update(rt[i], x, 1);
        }
    }
    for (int i = 1; i <= q; ++i) {
        int op, x, y, z;
        cin >> op;
        if (op == 1) {
            cin >> x >> y;
            a[++m] = y;
            insert(x, m);
            update(rt[x], y, 1); 
        } else if (op == 2) {
            cin >> x;
            update(rt[x], a[tail[x]], -1);
            erase(x);
        } else if (op == 3) {
            cin >> len;
            ll all = 0, sum = 0;
            for (int j = 1; j <= len; ++j) {
                cin >> c[j];
                tmp[j] = rt[c[j]];
                all += siz[c[j]];
            }
            int mid = search((all + 1) >> 1);
            for (int j = 1; j <= len; ++j)
                sum += query(rt[c[j]], mid);
            if (sum * 2 > all)
                cout << mid << '\n';
            else
                cout << "-1\n";
        } else {
            cin >> x >> y >> z;
            link(x, y, z);
            merge(rt[x], rt[y]);
            rt[z] = rt[x];
        }
    }
    return 0;
}