题目信息

• 平台：牛客
• 题目：有趣的区间
• 题目链接

题目描述

给定长度为 n 的整数数组，统计满足条件的子区间数量。根据代码语义推断：区间内至少包含一个奇数时，该区间被视为“有趣”。

初步思路

1. 总子区间数为 n*(n+1)/2。
2. 只要扣掉“全为偶数”的子区间数，剩下的就是至少包含一个奇数的区间数。
3. 统计连续偶数段长度 len，每段贡献 len*(len+1)/2。

算法分析

• 核心：总区间数减去全偶区间数
• 技巧：用一个计数器累积连续偶数长度，遇到奇数就结算
• 正确性简述：任一区间要么含奇数要么全偶，两类互斥且覆盖全部，扣除全偶即可得到答案
• 时间复杂度：O(n)
• 空间复杂度：O(1)

代码实现（C++）

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;

    long long len = 0;
    long long total = n * (n + 1) / 2;  // 总区间数
    long long bad = 0;                  // 全偶区间数

    for (int i = 0; i < n; ++i) {
        long long a;
        cin >> a;
        if ((a & 1) == 0) {            // 偶数
            len++;
        } else {                        // 奇数，结算一段连续偶数
            bad += len * (len + 1) / 2;
            len = 0;
        }
    }

    bad += len * (len + 1) / 2;         // 处理末尾偶数段
    cout << (total - bad) << "\n";
    return 0;
}

测试用例

总结与反思

1. 这类“至少包含某类元素”的计数题，常用补集思路更直接。
2. 连续段计数公式要记牢：len*(len+1)/2。