题解 | 有趣的区间（补集思想+组合数学）

很显然的补集思想+组合数学。不难得出包含任意奇数的区间都为有趣的区间，单步容斥可得所有区间个数减去无趣区间个数即为有趣区间个数，而无趣区间为全为偶数的区间。优化计数可用组合数学，即连续的最大无趣区间包含的无趣区间个数只与区间长度有关，因此可实现时间复杂度为的计数。

天冷了，请多喝热水，祝您拥有美好的一天！

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
int n, a[N];
signed main() {
    cin>>n;
    int ans=n*(n-1)/2+n, cnt=0;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        if(a[i]%2==0) ++cnt;
        else {
            if(cnt) ans-=cnt*(cnt-1)/2+cnt;
            cnt=0;
        }
    }
    if(cnt) ans-=cnt*(cnt-1)/2+cnt;
    cout<<ans;
}