自动搬运

查看原文

来自洛谷，原作者为

	EXODUS I love you this much

搬运于2025-08-24 22:34:48，当前版本为作者最后更新于2022-09-03 21:32:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part 1：前言

图论建模好题！

Part 2：正文

首先观察题目中所给的条件

在这里不妨令 $A_x\geq A_y$，将其分解为二进制，并把位数对齐，在这里我们假设 $A_x,A_y$ 分解后的结果如下。

不难发现这是一种符合条件的情况，你发现了什么？

首先摆出结论，令 $\text{highbit}(x)$ 表示 $x$ 的最高位 $1$ 的位置（从高位到低位），$\text{zero}(x,pos)$ 表示 $x$ 的第 $pos$ 位是否是 $0$，则有 $\text{zero}(A_x,\text{highbit}(A_y))=1$。

考虑如何证明，若 $\text{zero}(A_x,\text{highbit}(A_y))=0$，则异或后结果的第 $\text{highbit}(A_y)$ 位必然是 $0$，由于异或后第 $1,2,...,\text{highbit}(A_y)-1$ 位与异或前的均相同，所以此时有 $A_x\oplus A_y<A_x$。此时如果暴力建边，可以通过维护并查集的方式维护连通块。

注意到 $\text{zero}(A_x,\text{highbit}(A_y))=1$ 与 $A_x\oplus A_y>\max(A_x,A_y)$ 互为充要条件，所以我们可以多维护 $30$ 个并查集，分别表示每一位，然后对每一位 $j$ 记录是否存在 $i$ 使得 $\text{highbit}(A_i)=j$ 以及是否存在 $i$ 使得 $\text{zero}(A_i,j)=1$。接下来对于每个 $A_i$，判断他所有有 $0$ 的位 $x$ 是否存在 $j$，使得 $\text{highbit}(A_j)=x$，以及对其最高位 $y$ 是否存在 $j$ 使得 $\text{zero}(A_j,y)=1$，由于上述的处理，这个可以 $O(1)$ 做到。如果存在上述两种情况的话就直接合并它与对应位数的并查集。

输出的时候直接输出该并查集中的 $B$ 的和，带权并查集解决。由于我没写按秩合并，所以时间复杂度是 $O(n\log^2n)$ 的。

Part 3：代码

bool DataS=0,FilE=0;
int T;
void init(){
	return;
}
const int N=2e5+7,B=37;
int n;
int a[N],b[N];
int fa[N],sum[N],hib[N];
bool vis1[N],vis2[N];
int find(int i){while(i!=fa[i])i=fa[i]=fa[fa[i]];return i;}
void merge(int x,int y){x=find(x),y=find(y);if(x==y)return;fa[x]=y,sum[y]+=sum[x];}
signed main(){
	if(FilE){
		freopen("test.in","r",stdin);
		freopen("test.out","w",stdout);
	}
	T=(DataS?read():1);
	while(T--){
		init();
		n=read();
		for(int i=1;i<=n;i++)a[i]=read();
		for(int i=1;i<=n;i++){
			b[i]=read();
			fa[i]=i,sum[i]=b[i];
		}
		int bit=30;
		for(int i=1;i<=bit+1;i++)fa[i+n]=i+n;
		for(int i=1;i<=n;i++){
			for(int j=bit,flag=1;~j;j--){
				if((a[i]&(1<<j))&&flag)vis1[j]=1,flag=0,hib[i]=j;
				if((!(a[i]&(1<<j)))&&(!flag))vis2[j]=1;
			}
		}
		for(int i=1;i<=n;i++){
			if(vis2[hib[i]])merge(i,hib[i]+n+1);
			for(int j=hib[i],flag=1;~j;j--){
				if(!(a[i]&(1<<j))&&vis1[j])merge(i,j+n+1);
			}
		}
		for(int i=1;i<=n;i++){
			int x=find(i);
			printf("%lld\n",sum[x]);
		}
	}
	return 0;
}

Part 4：后文

点赞再走吧（可怜