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