NC253360. qsgg and Subarray
描述
给定一个长度为 数组
。
你想知道有多少个子区间
和为
，即
。
此处表示位运算
操作。
输入描述
输入共
行。
第一行一个整数表示
。
接下来一行，
个整数表示
。
输出描述
输出一个整数，表示满足条件的子区间 ![[l,r]](https://hr.nowcoder.com/equation?tex=%5Bl%2Cr%5D)
个数。
示例1
输入:
6 1 3 7 15 6 4
输出:
3
说明:
三个区间，分别是C++ 解法, 执行用时: 298ms, 内存消耗: 4352K, 提交时间: 2023-08-12 09:56:54
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int n,a[N],x=N,k,last[34];
long long ans=0;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
k=a[i];
x=N;
for(int j=1;j<=32;j++)
{
if(k&1) x=min(x,last[j]);
else last[j]=i;
k>>=1;
}
if(x==N) x=i;
ans+=x;
}
cout<<ans<<'\n';
return 0;
}