有趣的区间

NC231997. 有趣的区间

描述

给出一个长度为 $n$ 的数组 $A$ ，下标从 $1$ 开始， $A_1,A_2,...,A_n$ 。定义一个区间 $[l,r]$ 是“有趣的区间”，当且仅当 $A_l \mid A_{l+1} \mid A_{l+2} \mid ... \mid A_{r-1} \mid A_{r}$ 结果为奇数。

$a \mid b$ 表示 $a$ 按位或 $b$ （按位或运算符“ $\mid$ ”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的两个二进位有一个为 $1$ 时，结果位就为 $1$ ）。

求“有趣的区间”的个数，两个区间 $[L1,R1],[L2,R2]$ 相同，当且仅当 $L1=L2$ 且 $R1=R2$ 。

输入描述

第一行包含一个整数 $n$ $(1\le n\le 5e5)$ ，表示数组 $A$ 的长度。

第二行包含 $n$ 个整数，分别表示数组 $A$ 的 $n$ 个元素，其中 $0\le A_i\le 1e9$ 。

输出描述

一行包含一个整数，表示 ”有趣的区间“ 的个数。

示例1

输入:

2
2 1

输出:

说明:

”有趣的区间“ 有

$[1,2]$ $($ $2 \mid 1 = 3$ 是奇数 $)$

$[2,2]$ $($ $1$ 是奇数 $)$

共 $2$ 个。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 206ms, 内存消耗: 504K, 提交时间: 2022-01-14 19:44:04

#include<bits/stdc++.h>
using namespace std;
int n;
long long int ans=0,x,l;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		if(x&1) l=i;
		ans+=l; 
	}
	cout<<ans;
	return 0;
}

C 解法, 执行用时: 84ms, 内存消耗: 356K, 提交时间: 2022-01-13 21:43:33

#include <stdio.h>
int main()
{
	int n,m,a;
    long long sum=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a);
		if(a&1)m=i;
		sum+=m;
	}
	printf("%lld",sum);
	return 0;
}

Python3 解法, 执行用时: 249ms, 内存消耗: 63688K, 提交时间: 2022-02-09 09:29:47

n=int(input())
a=list(map(int,input().split()))
tot=0
ans=0
for i in range(0,n):
    if a[i]&1:
        tot=i+1
    ans+=tot
print(ans)