BZOJ4300 绝世好题

Description

给定一个长度为(n)的数列(a_{i})，求(a_{i})的子序列(b_{i})的最长长度，满足(b_{i} & b_{i-1} eq 0(2 le i le len))。

Input

输入文件共(2)行。
第一行包括一个整数(n)。
第二行包括(n)个整数，第(i)个整数表示(a_{i})。

Output

输出文件共一行。
包括一个整数，表示子序列(b_{i})的最长长度。

Sample Input

3
1 2 3

Sample Output

2

HINT

(n le 100000,ai le 2 imes 10^{9})

好吧，这题我是骗掉的。(f_{i})表示以(a_{i})结尾的最长子序列，将序列按(f)插入平衡树中。之后从枚举(a_{i})，每次从树中从大到小取出(f_{j})，若合法便把(a_{i})接到(a_{j})后，break。将(f_{i})更新，插入平衡树。

#include<cstdio>
#include<cstdlib>
#include<set>
using namespace std;

#define maxn (100010)
int N,ans,f[maxn],A[maxn];
struct cmp { inline bool operator ()(int a,int b) { return f[a] != f[b]?(f[a]>f[b]):(a>b); } };
set <int,cmp> S;

inline int gi()
{
	char ch; int ret = 0,f = 1;
	do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');
	if (ch == '-') f = -1,ch = getchar();
	do ret = ret*10+ch-'0',ch = getchar(); while (ch >= '0'&&ch <= '9');
	return ret*f;
}

int main()
{
	freopen("4300.in","r",stdin);
	freopen("4300.out","w",stdout);
	N = gi();
	for (int i = 1;i <= N;++i) A[i] = gi();
	for (int i = 1;i <= N;++i)
	{
		set <int,cmp> :: iterator it,ed;
		f[i] = 1;
		for (it = S.begin(),ed = S.end();it != ed;++it)
			if (A[i]&A[*it]) { f[i] = f[*it]+1; break; }
		S.insert(i);
	}
	for (int i = 1;i <= N;++i) if (f[i] > ans) ans = f[i];
	printf("%d",ans);
    fclose(stdin); fclose(stdout);
	return 0;
}