检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。
#题面
#题目描述
Abathur 采集了一系列 Primal Zerg 的基因样本,这些基因构成了一个完整的进化链。为了方便,我们用 这 个正整数描述它们。
一个基因 可以进化为序列中在它之后的基因 。这个进化的复杂度,等于 的值,其中 是二进制或运算。
Abathur 认为复杂度小于 的进化的被认为是温和的。它希望计算出温和的进化的对数。
#输入格式
第一行包含两个整数 。
接下来一行包含 这 个正整数,描述这 个基因。
#输出格式
第一行包含一个整数,表示温和的进化的对数。
#样例输入输出
样例输入 #1
4 6
1 3 5 1
样例输出 #1
2
#数据范围
对于 的数据,;
对于 的数据,,,。
#思路
有一个比较显然的性质:或起来的数一定越来越大。那么在确定一个右端点之后可以使用双指针枚举左端点,使用线段树维护区间按位或和即可。或者确定左端点使用二分枚举右端点也可以,在此不作过多叙述。
#代码
1 |
|