洛谷P7973 [KSN2021] Binary Land 题解

题目链接：P7973 [KSN2021] Binary Land

题意：

给定一张 \(N\) 个点的图，每个点有权值 \(A_i\) 和价值 \(B_i\)。

两个点 \(x,y\) 之间存在一条无向边当且仅当 \(A_x\text{ xor }A_y>\max(A_x,A_y)\)。

你需要对于 \(i=1,2,\cdots n\) 依次求出点 \(i\) 所在连通块中所有点的价值和。

输入格式：

第一行输入一个正整数 \(N\)。

第二行输入 \(N\) 个正整数 \(A_i\)。

第三行输入 \(N\) 个正整数 \(B_i\)。

输出格式：

输出 \(N\) 行，第 \(i\) 行包含一个整数，代表点 \(i\) 所在连通块中所有点的价值和。

数据范围：

对于所有数据，\(1 \leq N \leq 10^5\)，\(1 \leq A_i \leq 2^{30}-1\)，\(1 \leq B_i \leq 10^9\)。

根据常规套路，钦定 \(A_x \ge A_y\) ，则边 \((x,y)\) 存在的充要条件为：\(A_x\) 的第 「 \(A_y\) 的最高位 」位为 \(0\) 。

容易证明这种情况下，\(A_x \operatorname{xor} A_y > A_x\) 。但是因为 \(y\) 的数量很多，所以考虑用并查集维护连通性。

直接把 \(x,y\) 合并并不是很方便统计，我们可以加入 \(64\) 个点，表示每一个二进制位，然后通过他们连接 \(x,y\) 。

时间复杂度 \(\mathcal{O}(n \log^2 n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 225))

char vis1[35],vis2[35];
int n,a[N],b[N],f[N],val[N],hib[N];
void init() { for(int i = 1; i <= n + 66; i++) f[i] = i; }
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void merge(int x,int y) {
    x = find(x), y = find(y); if(x != y) { f[x] = y; val[y] += val[x]; }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; init();
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) { cin >> b[i], val[i] = b[i]; }
    for(int i = 1; i <= n; i++)
    {
        int j = 64 - __builtin_clzll(a[i]);
        vis1[j] = true; hib[i] = j;
        while(j--) if(!(a[i] & (1 << (j - 1)))) vis2[j] = true;
    }
    for(int i = 1; i <= n; i++)
    {
        if(vis2[hib[i]]) merge(i, hib[i] + n);
        for(int j = 64 - __builtin_clzll(a[i]); j; j--) {
            if(!(a[i] & (1 << (j - 1))) && vis1[j]) merge(i, j + n);
        }
    }
    for(int i = 1; i <= n; i++) cout << val[find(i)] << '\n';
    return 0;
}