[Medium] CF1849F XOR Partition

简要题意

给定一个大小为 $n$ 的集合 $S$，你需要将其划分为两个集合，使得每一个集合的最小异或对的最小值最大，输出一组合法的方案。

$2\leq n\leq 2\times 10^5,0\leq S_i<2^{30}$。

思路

直觉上肯定有一个贪心：每次选出最小异或对，将其拆散，划分到不同的集合，无法操作为止。这个方法的正确性是显然的，因为每次都可以让答案严格减小。

但同时也可以发现一个问题：如何判断划分到哪一个集合？注意到出题人为什么不划分到 $k$ 个集合而是划分到两个集合中呢？故划分到两个集合一定有其特殊性质，那么不难联想到二分图。

对于两个元素 $(S_i,S_j)$，连边 $(i,j)$，边权为 $S_i\oplus S_j$，那么我们需要找一个导出二分子图，使得每个颜色划分成一个集合，答案最大。不过导出二分图我们不大熟悉，而生成树我们熟悉，又因为树已经可以确定染色方法了，因此可以考虑最小生成树。

为什么最小生成树就足够了呢？因为 Kruskal 的过程就是我们的贪心啊！

现在我们只需要求出这个完全图的最小生成树，然后染色就可以得到答案。

如何求出最小生成树？不妨使用 Boruvka 算法，使用可合并的 01 trie 维护。时间复杂度 $O(n\log n\log V)$。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int n, a[N];

template<int N>
struct trie {
    int trie[N][2], siz[N], idt[N], tot;

    void insert(int u, int x, int id){
        for(int i=29;~i;i--){
            bool t = (x >> i) & 1;
            if(!trie[u][t]) trie[u][t] = ++tot;
            u = trie[u][t], siz[u]++;
        }
        idt[u] = id;
    }

    pair<int,int> query(int u, int v, int x){
        int val = 0;
        for(int i=29;~i;i--){
            bool t = (x >> i) & 1;
            if(siz[trie[u][t]] - siz[trie[v][t]]) u = trie[u][t], v = trie[v][t];
            else u = trie[u][t ^ 1], v = trie[v][t ^ 1], val |= 1 << i;
        }
        return {idt[u], val};
    }

    int merge(int x, int y){
        if(!x || !y) return x | y;
        trie[x][0] = merge(trie[x][0], trie[y][0]);
        trie[x][1] = merge(trie[x][1], trie[y][1]);
        siz[x] = siz[trie[x][0]] + siz[trie[x][1]];
        idt[x] |= idt[y];
        return x;
    }
};

using i64 = long long;
trie<N << 6> t;
int rt[N];
int fa[N], tag[N], wgt[N];
pair<int,int> edg[N];
bool bel[N];
vector<int> g[N];

int find(int x){ return fa[x] == x ? fa[x] : find(fa[x]); }

void boruvka(){
    iota(fa + 1, fa + n + 1, 1);
    bool flag = 1;
    while(flag){
        flag = 0;
        fill(wgt + 1, wgt + n + 1, INT_MAX);
        for(int i=1;i<=n;i++){
            int fx = find(i);
            auto [y, w] = t.query(rt[0], rt[fx], a[i]);
            if(!y) continue;
            int fy = find(y);
            if(wgt[fx] > w) tag[fx] = fy, wgt[fx] = w, edg[fx] = {i, y};
        }
        for(int i=1;i<=n;i++){
            if(wgt[i] != INT_MAX && find(i) != find(tag[i])){
                rt[find(i)] = t.merge(rt[find(i)], rt[find(tag[i])]);
                fa[find(tag[i])] = find(i), flag = 1;
                g[edg[i].first].push_back(edg[i].second);
                g[edg[i].second].push_back(edg[i].first);
            }
        }
    }
}

void dfs(int u, int fa){
    bel[u] = !bel[fa];
    for(int v : g[u]){
        if(v != fa) dfs(v, u);
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    rt[0] = ++t.tot;
    for(int i=1;i<=n;i++){
        t.insert(rt[i] = ++t.tot, a[i], i);
        t.insert(rt[0], a[i], i);
    }
    boruvka(), dfs(1, 0);
    for(int i=1;i<=n;i++) cout << bel[i];
    return 0;
}

// Written by xiezheyuan