【BZOJ4300】绝世好题

Description
给定一个长度为n的数列ai，求ai的子序列bi的最长长度，满足bi&bi-1!=0(2<=i<=len)。

Input
输入文件共2行。
第一行包括一个整数n。
第二行包括n个整数，第i个整数表示ai。

Output
输出文件共一行。
包括一个整数，表示子序列bi的最长长度。

Sample Input
3
1 2 3
Sample Output
2
HINT

对于100%的数据，1<=n<=100000，ai<=10^9。

Source

By Oxer

给泥萌一个黑科技函数
黑科技
再也不用先手写转二进制了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define lowbit(x) (x&(-x))
#define GET (ch>='0'&&ch<='9')
using namespace std;
int n,x,ans,a[40];
void in(int &x)
{
    char ch=getchar();x=0;int flag=1;
    while (!GET)    flag=ch=='-'?-1:1,ch=getchar();
    while (GET) x=x*10+ch-'0',ch=getchar();x*=flag;
}
int main()
{
    in(n);
    while (n--)
    {
        in(x);int num=0,t;
        for (int i=x;i;i-=lowbit(i))    num=max(num,a[__builtin_ctz(i)]);
        ans=max(ans,++num);
        for (;x;x-=lowbit(x))   t=__builtin_ctz(x),a[t]=max(a[t],num);
    }
    cout<<ans<<endl;
}