题解：P7384 「EZEC-6」分组

· · 题解

提供一种 O(n+\log v \alpha(\log v)) 的做法。

80 分做法同官解的 80 分。

考虑如何优化，发现可以在一定有两个集合合并时再拆位合并。于是记录每一位所在集合的并，需要时（当前处理的数有一位为 1 且这位不在集合并中）再合并。每次 O(\log v\alpha(\log v)) 合并一次，再 O(\log v) 求集合的并即可做到 O(n+\log v \alpha(\log v))。

代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7+100;
int n;
int a[N],f[N],vv[N],g[N];
bool v[N];
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
#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;
}
signed main()
{
    read(n);
    int x,y,z=0,ans=0;
    for(int i=1;i<=n;i++)read(a[i]),g[i]=i;
    for(int i=0;i<63;i++)f[i]=i;
    for(int i=1;i<=n;i++)
    {
        z|=a[i];
        if(!a[i]){ans++;continue;}
        if((vv[__builtin_ctzll(a[i]&-a[i])]&a[i])>=a[i])continue;
        x=find(__builtin_ctzll(a[i]&-a[i])),y=0;
        for(int j=0;j<63;j++)
        {
            if(a[i]&(1ll<<j))f[find(j)]=x;
            if(find(j)==x)y|=1ll<<j;
        }
        x=find(x);
        for(int j=0;j<63;j++)if(find(j)==x)vv[j]=y;
    }
    for(int i=0;i<63;i++)
    {
        if(!(z&(1ll<<i)))continue;
        if(!v[find(i)])v[find(i)]=1,ans++;
    }
    cout<<ans;
}