题目来源：https://ac.nowcoder.com/acm/problem/231997
这段时间一直在参加训练，基本上每天一场VP，回寝室就属于懒得动的情况，所以一直没有更新嘿嘿（求放过）。
本题牛客官方定数1500，个人认为大差不差，思维量为主，代码实现其实很简单。首先先理解按位或操作：对于两个数字的二进制序列靠右对齐，然后每位进行或运算。这时候我们要提到两个引理：
引理1：任何数字都可以用 2 的幂次进行表示。（这个应该都懂，就是二进制的形式化表述）
引理2：进一步，任何偶数的二进制位最后一位必然为 0，而奇数必然为 1.（这个同样好理解，因为二进制序列的最后一位是 2 的 0 次）
基于这两个引理，我们不难对题目的定义进行转换：如果数组中区间 [ l , r ] 的元素进行按位或运算的结果为一个奇数，意味着这个序列在该区间中至少要存在一个奇数。至此，我们对题意的解析已经结束了，也就是说，我们的任务是找出给定数组中含有奇数的子数组的个数。
如果直接尝试用这个思路写代码，你应该能料想得到代码处理起来会有多烦，5e5 的数据范围也不是和你开玩笑的。所以正难则反的思路，我们不妨把求解转化一下，变成求出给定数组中只含有偶数的子数组个数，然后再用整个数组的子数组个数减一下，就可以得到答案。此时再进一步思考算法实现，我们不难想到可以用滑动窗口的方式进行统计。
对于长度为 n 的一个数组，我们知道子数组长度从 n 到 1 一共有 1, 2, 3, ... n-2, n-1, n 种取法。所以很容易发现用等差数列求和就可以求出所有的子数组个数。同理，在维护偶数窗口的时候，我们就可以通过窗口长度计算子数组个数。具体的，如果窗口的长度为 1, 我们就对总的子数组个数 tot 减去 1，如果窗口的长度延伸到 2，不难发现只要再减去 2 即可。
具体实现：读入数组长度 n 和所有元素，在输入的时候就可以对元素进行处理。由于这里只要求个数，并不关心实际的元素值为多少，所以我们不妨直接把奇数统一设置为 1，偶数则统一设置为 0.接下来分别开一个左右指针，维护窗口内的元素全部为 0 即可。下面是 AC Code：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
ll n;
cin>>n;
ll res=(n+1)*n/2;
vector<ll> a(n+1);
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]&1) a[i]=1;
else a[i]=0;
}
int l=0;
while(l<n)
{
if(a[l]==0)
{
int k=1;
res-=k;
l++;
while(l<n&&a[l]==0)
{
k++;
l++;
res-=k;
}
}
l++;
}
cout<<res<<endl;
return 0;
}
Comments NOTHING