题解 | 有趣的区间

#include <iostream>
using namespace std;
using ll=long long;  // 用ll别名表示long long，避免溢出（n可能很大）

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    // 算法核心思想：
    // 1. 总区间数 = n*(n+1)/2 （所有可能的子区间数量）
    // 2. 不符合条件的区间数 = 所有全偶数子区间的数量（按位或结果为偶数）
    // 3. 有趣区间数 = 总区间数 - 不符合条件的区间数（至少含一个奇数，按位或为奇数）

    ll n;
    cin>>n;  // 输入数组长度
    
    // 步骤1：计算数组的总区间数（所有可能的子区间数量）
    ll sum=(n*(n+1))/2;  // 总区间数公式：长度为n的数组，子区间数为n(n+1)/2
    
    ll t=0;             // 临时变量：记录当前连续偶数的个数
    ll d_sum=0;         // 累计变量：记录所有全偶数子区间的总数（不符合条件的区间数）
    
    // 步骤2：遍历数组，统计所有连续偶数段能形成的全偶区间数
    for(ll i=1;i<=n;i++){
        ll A;
        cin>>A;  // 输入数组的第i个元素
        
        // 情况1：当前元素是偶数 → 加入当前连续偶数段，计数+1
        if(A%2==0){
            t++;  // 连续偶数的长度加1
            
            // 边界处理：遍历到最后一个元素时，若仍在连续偶数段中，需结算该段的区间数
            if(i==n){
                d_sum+=(t*(t+1))/2;  // 长度为t的连续偶数段，能形成t(t+1)/2个全偶区间
            }
        }
        // 情况2：当前元素是奇数 → 结算之前的连续偶数段（若有）
        else{
            // 如果存在未结算的连续偶数段
            if(t!=0){
                d_sum+=(t*(t+1))/2;  // 计算该段的全偶区间数并累加到d_sum
                t=0;                 // 重置连续偶数计数，开始新的统计
            }
        }
    }
    
    // 步骤3：计算并输出有趣区间数 = 总区间数 - 全偶区间数
    cout<<sum-d_sum;
    return 0;
}