本文共 1927 字，大约阅读时间需要 6 分钟。

考虑$x\oplus y=gcd(x,y)$的情况应该是非常少的

不妨设$x>y$

由于$x\oplus y>=x-y>=gcd(x,y)$

显然等号应该同时取到,得到$x\oplus y=x-y=gcd(x,y)$

枚举约数$k$作为$gcd(x,y)$

那么$x,y$一定是$k$的倍数,所以可以枚举$k$的倍数作为$y$

如果满足上面那个$x,y$的关系就是合法的关系,把这些关系存起来

显然预处理这些关系的复杂度是调和级数的复杂度

那么现在只需要对一个集合维护一个桶即可

修改集合内某个点的点权,只需要枚举这个点权可能的关系即可,直接从桶里面取数

合并两个集合,使用启发式合并,小的合并到大的上面

然后桶数组也累加

#include 
   
    using namespace std;const int maxn = 3e5+10;vector
    
     rule[maxn];int n,m;int gcd(int a,int b){
    return b==0?a:gcd(b,a%b); }void init(int mx){
   	for(int i=1;i<=mx;i++)	for(int j=i;j+i<=mx;j+=i)	{
   		int y = j, x = j+i;		if( (x^y)==x-y && x-y==gcd(x,y) )		{
   			rule[x].push_back( y );			rule[y].push_back( x );		}	}}int fa[maxn],siz[maxn],val[maxn];long long ans;int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]); }unordered_map
     
      mp[maxn];vector
      
       vec[maxn];void join(int x,int y){
   	int fl = find( x ), fr = find( y );	if( fl==fr )	return;	if( siz[fl]>siz[fr] )	swap(fl,fr);//	if( mp[fl].size()>mp[fr].size() )	swap(fl,fr);	for(auto v:mp[fl] )	for(auto r:rule[v.first] )		if( mp[fr].count(r) )			ans += 1ll*v.second*mp[fr][r];	for(auto v:mp[fl] )	mp[fr][v.first] += v.second;	mp[fl].clear(); 	siz[fr] += siz[fl], fa[fl] = fr;}int main(){
   	init(200000);	cin >> n >> m;	for(int i=1;i<=n;i++)	{
   		scanf("%d",&val[i] );		fa[i] = i, siz[i] = 1, mp[i][val[i]]++;	}	while( m-- )	{
   		int type,x,y; scanf("%d%d%d",&type,&x,&y);		if( type==1 )			siz[x] = 1, fa[x] = x, val[x] = y, mp[x][val[x]]++;		else if( type==2 )	join(x,y);		else		{
   			//把节点x的权值修改为y			int zu = find( x );			mp[zu][val[x]]--;			for(auto v:rule[val[x]] )	ans -= mp[zu][v];			val[x] = y;			for(auto v:rule[val[x]] )	ans += mp[zu][v];			mp[zu][val[x]]++;		}		printf("%lld\n",ans);	}}
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/117235121 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！