YC307B [ 20240625 CQYC省选模拟赛 T2 ] 一个题（ynoi）

题意

你需要维护一个可重集 \(S\)，支持插入删除以及查询最大的方案使得给定正整数 \(k\)，划分为 \(k\) 个非空子集的按位与结果之和最大。

\(n \le 10 ^ 5\)

Sol

先上个 trie。

然后考虑一次查询怎么搞。

先转化一下，如果需要划分为 \(k\) 个子集，显然需要合并 \(n - k\) 次。

我们只需要保证每次划分操作不劣即可。

从高位到低位考虑每一位，显然只需要考虑当前位最大即可。

注意到每次合两堆只有几种情况，显然 \(0\) 与 \(0\) 合一定不劣。

因为你如果合别的，一定会少 \(1\)。

所以考虑找出当前位是 \(0\) 的数字个数，直接判断和当前需要合的个数 \(k'\) 即可。

若当前可以用 \(0\) 合光就直接合掉，这样剩下一定会最优，直接递归到下一层 \(1\) 即可。

而没法合完的情况怎么办呢，你考虑先把所有 \(0\) 合起来，然后用个 \(\text{set}\) 把这个东西存下来。

这样你存起来的数只会有 \(\log\) 个，因为你在走 \(1\) 的子树时，有可能可以把别的数字合过来，所以要存一下。

时间复杂度：\(O(n \log ^ 2 n)\)。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <set>
#include <vector>
#include <unordered_set>
#define int long long
using namespace std;
#ifdef ONLINE_JUDGE

/* #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) */
/* char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf; */

#endif
int read() {
    int p = 0, flg = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') flg = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        p = p * 10 + c - '0';
        c = getchar();
    }
    return p * flg;
}
void write(int x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
bool _stmer;

const int N = 1e5 + 5, inf = (1 << 30) - 1;

array <int, N * 33> edge, isl, siz, fa;
array <array <int, 2>, N * 33> nex;

int cnt = 1;

void pushup(int x) {
    x = fa[x];
    while (x) {
        siz[x] = siz[nex[x][0]] + siz[nex[x][1]];
        isl[x] = isl[nex[x][0]] & isl[nex[x][1]];
        edge[x] = edge[nex[x][0]] + edge[nex[x][1]];
        x = fa[x];
    }
}

void insert(int x) {
    int p = 1;
    for (int i = 30; ~i; i--) {
        if (!nex[p][x >> i & 1])
            cnt++, fa[cnt] = p, nex[p][x >> i & 1] = cnt;
        p = nex[p][x >> i & 1];
    }
    siz[p]++, isl[p] = x, edge[p] += x;
    pushup(p);
}

void delet(int x) {
    int p = 1;
    for (int i = 30; ~i; i--)
        p = nex[p][x >> i & 1];
    siz[p]--, isl[p] = siz[p] ? (bool)siz[p] * x : inf, edge[p] -= x;
    pushup(p);
}

int query(int k) {
    multiset <int> arc;
    k = siz[1] - k;
    /* cerr << k << endl; */
    int p = 1, ans = 0;
    for (int i = 30; ~i; i--) {
        int tp = siz[nex[p][0]] - 1;
        for (auto t : arc)
            if ((t >> i & 1) ^ 1) tp++;
        if (!~tp) { p = nex[p][1]; continue; }
        if (tp > k) {
            int res = edge[nex[p][1]];
            unordered_set <int> tp0;
            for (auto t : arc)
                if (t >> i & 1) res += t, tp0.insert(t);
            for (auto t : tp0) arc.erase(t);
            ans += res, p = nex[p][0];
        }
        else {
            k -= tp;
            int res = isl[nex[p][0]];
            /* cerr << i << " " << p << " " << nex[p][0] << endl; */
            unordered_set <int> tp0;
            for (auto t : arc)
                if ((t >> i & 1) ^ 1) res &= t, tp0.insert(t);
            for (auto t : tp0) arc.erase(t);
            arc.insert(res), p = nex[p][1];
        }
    }
    ans += (siz[p] - k) * isl[p];
    for (auto t : arc) ans += t;
    return ans;
}

bool _edmer;
signed main() {
    cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
    int n = read(), q = read();
    isl[0] = inf;
    for (int i = 1, x; i <= n; i++)
        x = read(), insert(x);
    while (q--) {
        int op = read(), k = read();
        if (op == 1) insert(k);
        if (op == 2) delet(k);
        if (op == 3) write(query(k)), puts("");
    }
    return 0;
}