sto a___ orz

这里介绍一种奇怪的 $O(n\sqrt{\log a_{i}})$ 的做法：

我们显然有一个二进制拆位的 $O(n\log a_i)$ 的做法，把一个数的所有 $1$ 用并查集合并即可。

对于 $\operatorname{popcount}\le \sqrt{\log a_{i}}$ 的部分，和上面做法一样，每次跳 $\operatorname{lowbit}$ 并查集合并。

对于 $\operatorname{popcount}> \sqrt{\log a_{i}}$ 的部分，我们开一个数组，每次加入这样的一个数就扫一遍数组，如果有相交的就或起来，这样数组内一定没有相交元素，元素数量就一定小于 $\sqrt{\log a_{i}}$。

代码：

#include<cstdio>
#include<list>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {
	r=0;bool w=0; char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
	r=w?-r:r;
}
int n,c[70],mark[70],cnt;
int find(int x){
	while(x!=c[x])x=c[x]=c[c[x]];
	return x;
}
void merge(int x,int y){
	x=find(x),y=find(y);
	if(x!=y)c[y]=x;
}
long long b[70];
int main(){
	read(n);
	for(int i=0;i<64;i++)c[i]=i;
	int ans=0;
	for(int i=1;i<=n;i++){
		long long x;
		read(x);
		if(x!=0){
			int d=__builtin_popcountll(x);
			if(d<=8){
				int p=__builtin_ctzll(x);
				x&=x-1;
				mark[p]=1;
				while(x){
					int d=__builtin_ctzll(x);
					x&=x-1;
					mark[d]=1;
					merge(p,d);
				}
			}else{
				static long long d[70];
				int ct=0;
				for(int i=1;i<=cnt;i++)if(x&b[i])x|=b[i];else d[++ct]=b[i];
				d[++ct]=x;
				for(int i=1;i<=ct;i++)b[i]=d[i];
				cnt=ct;
			}
		}else ++ans;
	}
	for(int i=1;i<=cnt;i++){
		long long &x=b[i];
		int p=__builtin_ctzll(x);
		x&=x-1;
		mark[p]=1;
		while(x){
			int d=__builtin_ctzll(x);
			x&=x-1;
			mark[d]=1;
			merge(p,d);
		}
	}
	for(int i=0;i<64;i++)ans+=mark[i]&&c[i]==i;
	printf("%d\n",ans);
	return 0;
}