题解 | #满意的数字#

D. 注意到按位或的特性可以发现,二进制位变成1的位置永远不会变成0,所以可以考虑到,只需要区间内有1个奇数,那么一定就是有趣的奇数

那此时如何统计区间呢

我们之从当前数出发,统计以当前数为左区间的有趣区间数有多少,然后以每个数的奇偶性进行分类讨论

如果当前数为奇数,那么右边所有数以该数为左区间的数一定是有趣的区间 ans+=n-i+1

如果当前数为偶数呢？他只需要包含右边第一个奇数开始就是有趣的区间,先预处理出所有偶数右边的第一个奇数的下标,遇到偶数就加上右边第一个奇数为左区间的区间数 ans+=n-nxt[i]+1

Code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int a[500005];
int nxt[500005];
ll ans;
int j;
int main()
{
    cin>>n;
    for(int i = 1;i<=n;++i)
    {
        cin>>a[i];
        if(a[i]%2)
            j++;
    }
    int lastj = n+1;
    for(int i = n;i;i--)
    {
        if(a[i]%2)
            lastj = i;
        nxt[i] = lastj;
    }
    for(int i = 1;i<=n;++i)
    {
        if(a[i]%2)
            j--,ans+=n-i+1;
        else
            ans+=n-nxt[i]+1;
    }
   cout<<ans<<endl;
    return 0;
}