题解：P7384 「EZEC-6」分组

提供一种 O(n) 的做法。

加上了快读，快写。

吸氧仅需 384 毫秒。

思路：

按位思考。

输入 x，将 s 数组中的第 lowbit(x) 项或上 x（若 x 为 0，直接将答案加一）。

遍历 s 数组，每次都往后寻找到第一个相交的项。

随后合并，舍弃前者。

再遍历一遍，找出还剩下的组的数量。

#include<bits/stdc++.h>
#define int long long
using namespace std;
#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;
}
inline void write(int x){//快写
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
}
int n,s[60],x,cnt;
signed main(){//防止变成long long main
    read(n);
    for(int i=1;i<=n;i++){
        read(x);
        if(!x){//若x为0,可单独分组
            cnt++;
            continue;
        }
        s[signed(log2(x&-x))]|=x;//log2(x&-x)可理解为lowbit(x);
    }
    for(int i=0;i<60;i++){
        for(int j=i+1;j<60;j++){
            if(s[i]&s[j]){
                s[j]|=s[i];//必须合并
                s[i]=0;//舍弃
            }
        }
    }
    for(int i=0;i<60;i++){
        if(s[i]){
            cnt++;
        }
    }
    write(cnt);
    return 0;//功德圆满
}