发表于|更新于|题解
|总字数:601|阅读时长:2分钟|浏览量:|
题目大意
给出一个序列 aa，设 f(l,r)f(l,r) 表示 al∣al+1∣al+2∣⋯∣ara_l|a_{l+1}|a_{l+2}|\cdots|a_r，求 f(l,r)f(l,r) 有多少不同的值。
思路
显然，对于任意 ll，f(l,r)≤f(l,r+1)f(l,r)\le f(l,r+1)，也就是说，对于从同一个数开始的所有区间，它们的值一定是随长度增加而增加的，所以，我们假设有一个变量 tt，它从 ala_l 开始不停地与下一个数相或，这个 tt 的值增加的次数就是所有以 ala_l 为左端点的区间中不同的 f(l,r)f(l,r) 的值的数量，因为 tt 只会增大，不会变小。
那么我们怎么知道这个 tt 变大了多少次呢？考虑 tt 在什么情况下会变大，显然，tt 会变大，当且仅当原来 tt 为 00 的位变成了 11，而且每一位最多会变一次，所以，我们维护一个 nxtnxt 数组，用 nxti,jnxt_{i,j} 表示 aia_i 到 ana_n 这些数中第 jj 位为 11 的第一个数的下标，由于有些位可能同时变成 11，所以我们还需要对下标进行去重。
最终时间复杂度 O(nlogM)O(n\log M)，常数稍大。
参考代码
对于 nxtnxt 数组，这里采用的是滚动数组的方法，减小了一点空间复杂度。
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
struct QwQ
{
int val;
int id;
bool operator < (const QwQ &a) const
{
return val == a.val ? id < a.id : val < a.val;
}
};
QwQ t[30];
int n, mx, a[N], b[N*15], nxt[30];
ll ans;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = n; i >= 1; i--)
{
int x = a[i];
for(int j = 0; j <= 20; j++)
{
t[j] = (QwQ){nxt[j], j};
if((a[i]>>j)&1)
nxt[j] = i;
}
sort(t, t+21);
for(int j = 0; j <= 20; j++)
if(t[j].val)
{
if(!b[x] && (j == 0 || t[j].val != t[j-1].val))
{
ans++;
b[x] = 1;
}
x |= (1<<t[j].id);
}
if(!b[x])
{
ans++;
b[x] = 1;
}
}
printf("%lld", ans);
return 0;
}
|
