题目描述

给定n个数字a

₁, a

₂, ..., a

_n。

定义f(l, r) = a

_l| a

_l+1| ... | a

_r。

现在枚举(1 <= l <= r <= n)，问不同的f值一共有多少个。

输入描述:

第一行一个整数n表示数组大小 (1 <= n <= 100,000)； 第二行n个整数满足0 <= a

<= 1000,000。

输出描述:

输出一个整数表示不同的f值一共有多少个。

示例1

输入

31 2 0

输出

示例2

输入

101 2 3 4 5 6 1 2 9 10

输出

11 每输入一个数xi，就在前面的基础上算。前面有多少个是在1-(i-1),2-(i-1)....

1 #include 
          
            2 using namespace std; 3 const int N = 2e6+10; 4 set
           
             st[2]; 5 bool vis[N]; 6 int x, n, last, ans; 7 int main() { 8     cin >> n; 9     for(int i = 1; i <= n; i ++) {10         cin >> x;11         last = 1 - last;12         st[last].clear();13         set
            
              :: iterator it = st[1-last].begin();14         for(; it != st[1-last].end(); ++ it) {15             int y = (*it)|x;16             vis[y] = true;17             st[last].insert(y);18         }19         st[last].insert(x);20         vis[x] = true;21     }22     for(int i = 0; i < N; i ++) if(vis[i]) ans++;23     cout << ans << endl;24     return 0;25 }