Description

给定一个长度为 \(n\) 的数列 \(a_i\), 求 \(a_i\) 的子序列 \(b_i\) 的最长长度, 满足 \(b_i \land b_{i-1} \neq 0 (2 \leq i \leq n)\).

Input

输入文件共 \(2\) 行.

第一行包括一个整数 \(n\).

第二行包括 \(n\) 个整数, 第 \(i\) 个整数表示 \(a_i\).

Output

输出文件共一行.

包括一个整数, 表示子序列 \(b_i\) 的最长长度.

Sample Input

3
1 2 3

Sample Output

2

Data Range

对于 100% 的数据,\(1 \leq n \leq 10^5, a_i \leq 10^9\).

Explanation

最开始智障想了个 Trie 树来维护这堆玩意儿...... 然后动态删串;

结果发现根本没法考虑更多的情况 (又是一次想少了当成绝世水题的经典案例);

于是突然发现其实 \(O(n^2)\) 动规是可做的, 其实 Trie 树就是在优化动规而已;

所以我们发现每一个数到底选不选其实没有什么太大意义, 因为有了一个就多一份麻烦;

然后把每一个数拆成 \(32\) 位直接处理就可以了.

后来还一直和 @hld67890 大神争论到底是算 \(O(n)\) 还是算 \(O(n \log n)\). ...... 求大神给个靠谱一点的建议~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 200100, maxm = 60;

int dp[maxm],
    arr[maxn];
int n;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    // Picking data
    for (int i = 1; i <= n; i++) {
        int tmp = 0;
        for (int j = 0; j < 31; j++)
            if (arr[i] & (1 << j))
                tmp = max(tmp, dp[j] + 1);
        for (int j = 0; j < 31; j++)
            if (arr[i] & (1 << j))
                dp[j] = tmp;
    }
    int res = 0;
    for (int j = 0; j < 31; j++)
        res = max(res, dp[j]);
    printf("%d\n", res);
    return 0;
}