发现各位DL的时复和空复都太低了，所以给一种 逆天 的双log做法

满足 j<i 且 a[j]&a[i]!=0 的j才能对i有贡献 所以DP

设f[i]表示以i为结尾的最长子序列长度

为方便说明，设f[j]_k表示满足条件的f[j]是通过二进制下第k位向f[i]转移的

可以发现，对于每个a[i]的每个k，只有最后那个可向i转移的j有用

证明:

• 1.若f[j]可向f[i]转移，则最终的f[i]一定比此f[j]大 (否则就可让f[i]=f[j]+1，使结论继续成立)
• 2.将结论1推广到每个i，即可证明

那么，只需预处理每个a[i]的每个k的最后一个j,再对每个a[i]的每个k进行遍历就好了

可设s[k][i]为1到i的a[i]中，(a[i]>>k)&1 的数量

遍历每个a[i]的每个k时再二分查找就好了

感觉自己说的不大清楚

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],s[39][100005],f[100005];
void prepare(int a,int id)
{
	int cnt=0; 
	while(a){
		if(a&1) s[cnt][id]=1;
		cnt++;a>>=1;
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		prepare(a[i],i);
		for(int j=0;j<31;j++) s[j][i]+=s[j][i-1];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<31;j++)
		{
			int w;
			if((a[i]>>j)&1){
				w=lower_bound(s[j],s[j]+n+1,s[j][i]-1)-s[j];
				f[i]=max(f[i],f[w]+1);
			}
		}
	}
	cout<<*max_element(f+1,f+n+1);
	return 0;
}