S2OJ-1471进化序列（evolve）题解

题面

题目描述

$Abathur$ 采集了一系列 $Primal$ $Zerg$ 的基因样本，这些基因构成了一个完整的进化链。为了方便，我们用 $A_0,A_1,…,A_{n-1}$ 这 $n$ 个正整数描述它们。

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

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

输入格式

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

接下来一行包含 $A_0,A_1,…,A_{n-1}$ 这 $n$ 个正整数，描述这 $n$ 个基因。

输出格式

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

样例 1 输入

4 6
1 3 5 1

样例 1 输出

2

数据范围

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

题解

思路

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

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

代码实现

时间复杂度$O(nlog^2n)$

#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自带的计算机敲了半天）。

附：位运算性质总结