Blackops

初心易得，始终难守

0%

牛客练习赛16 E 求值

发表于 分类于 ，

题目描述

给定$n$个数字$a_1, a_2, …, a_n$。

定义$f(l, r)$ = $a_l | a_{l+1}| … | a_r$。
现在枚举$(1 \le l \le r \le n)$，问不同的$f$值一共有多少个。

输入描述:

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

输出描述:

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

示例1

输入

1
2
3
1 2 0

输出

1
4

示例2

输入

1
2
10
1 2 3 4 5 6 1 2 9 10

输出

1
11

题目链接：E.求值

赛后补题才会的（为什么感觉这题好像哪里见过233），枚举按位或的起始位置$L$，那么$a[L]$的第$i$位一旦在向右或的过程中变为$1$，那么之后这位再为$1$的数就不会产生贡献了，也就是说只有第一次让某位变$1$的数才有贡献，那么可以与预处理出第$i$个数字第$j$位向右的第一个（位置$i$本身不算）第$j$位同样为$1$的位置$i’$，对于所有的数，显然最坏情况是把所有位全或为$1$就可以停止了，那么枚举$a[L]$之后再得到$a[L]$所有位开始改变的第一个位置，按位置顺序去或这些有贡献的位置即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
typedef pair<int, int> pii;
typedef long long LL;
const int N = 1e5 + 7;
int arr[N], cnt[1 << 20], pos[N][20];

int main(void)
{
    int n, i, j;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    {
        scanf("%d", arr + i);
        for (j = 0; j < 20; ++j)
            if ((arr[i] >> j) & 1)
                pos[i][j] = i;
    }
    for (i = n - 1; i >= 1; --i)
    {
        for (j = 0; j < 20; ++j)
        {
            if (!pos[i][j])
                pos[i][j] = pos[i + 1][j];
        }
    }
    int ans = 0;
    vector<int>bitpos;
    for (i = 1; i <= n; ++i)
    {
        int s = arr[i];
        if (++cnt[s] == 1)
            ++ans;
        bitpos.clear();
        for (j = 0; j < 20; ++j)
        {
            if (arr[pos[i + 1][j]])
                bitpos.pb(pos[i + 1][j]);
        }
        sort(all(bitpos));
        for (auto &idx : bitpos)
        {
            s |= arr[idx];
            if (++cnt[s] == 1)
                ++ans;
        }
    }
    printf("%d\n", ans);
    return 0;
}