S2OJ-1471进化序列(evolve)题解

题面

题目描述

AbathurAbathur 采集了一系列 PrimalPrimal ZergZerg 的基因样本,这些基因构成了一个完整的进化链。为了方便,我们用 A0,A1,,An1A_0,A_1,…,A_{n-1}nn 个正整数描述它们。

一个基因 AxA_x 可以进化为序列中在它之后的基因 AyA_y。这个进化的复杂度,等于 AxAx+1...AyA_x | A_{x+1}...| A_y 的值,其中|是二进制或运算。

AbathurAbathur 认为复杂度小于 MM 的进化的被认为是温和的。它希望计算出温和的进化的对数。

输入格式

第一行包含两个整数 n,mn,m

接下来一行包含 A0,A1,,An1A_0,A_1,…,A_{n-1}nn 个正整数,描述这 nn 个基因。

输出格式

第一行包含一个整数,表示温和的进化的对数。

样例 1 输入

1
2
4 6
1 3 5 1

样例 1 输出

1
2

数据范围

对于 30%30\% 的数据,1n10001\le n\le 1000。 对于 100%100\% 的数据,1n100000,0m230,1Ai2301\le n\le100000,0\le m\le2^{30},1≤Ai≤2^{30}

题解

思路

看到求区间后首先想到了前缀和,然而或运算似乎不太支持前缀和,所以我们可以使用线段树来求区间或和,直接枚举是O(n2logn)O(n^2logn)的时间复杂度,显然过不去。

然后我们就可以想到或运算的一个特殊性质:一个数或上另一个数只会增加这个数或是不变,不会减少。通过这个性质我们就可以想到二分答案了。

代码实现-时间复杂度O(nlog2n)O(nlog^2n)

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<array>
#include<algorithm>
#include<cmath>
using namespace std;
using gg=long long;
array<gg,100010> v;
array<gg,400010> num;
void pushup(const gg &p)
{
num[p]=(num[p*2]|num[p*2+1]);
return;
}
void build(const gg &l,const gg &r,const gg &p)
{
if(l==r)
{
num[p]=v[l];
return;
}
gg mid=(l+r)/2;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
pushup(p);
return;
}
gg getsum(const gg &l,const gg &r,const gg &nl,const gg &nr,const gg &p)
{
if(nl>=l&&nr<=r)
{
return num[p];
}
gg mid=(nl+nr)/2,numtp=0;
if(mid>=l)
{
numtp=getsum(l,r,nl,mid,p*2);
}
if(mid+1<=r)
{
numtp|=getsum(l,r,mid+1,nr,p*2+1);
}
return numtp;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
//freopen("evolve.in","r",stdin);
//freopen("evolve.out","w",stdout);
gg n,m,ans=0;
cin>>n>>m;
for(gg i=1;i<=n;i++)
{
cin>>v[i];
}
build(1,n,1);
for(gg i=1;i<=n;i++)
{
gg l=i+1,r=n,mid,p=i;
while(l<=r)
{
mid=(l+r)/2;
if(getsum(i,mid,1,n,1)<m)
{
p=mid;
l=mid+1;
}
else
{
r=mid-1;
}
}
ans+=p-i;
}
cout<<ans<<'\n';
return 0;
}

总结

考试的时候想了挺长时间的,一开始还把或看成异或了,写了前缀和,最后过了样例测大样例的时候才看出来,浪费了一些时间。二分也是想了一会才想出来的(为了验证或运算的性质我还拿win10自带的计算机敲了半天)。

附:位运算性质总结