2026-01-17-牛客刷题笔记-有趣的区间

题目信息

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

题目描述

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

初步思路

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

算法分析

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

代码实现（C++）

#include<iostream>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);longlongn;cin>>n;longlonglen=0;longlongtotal=n*(n+1)/2;// 总区间数longlongbad=0;// 全偶区间数for(inti=0;i<n;++i){longlonga;cin>>a;if((a&1)==0){// 偶数len++;}else{// 奇数，结算一段连续偶数bad+=len*(len+1)/2;len=0;}}bad+=len*(len+1)/2;// 处理末尾偶数段cout<<(total-bad)<<"\n";return0;}

测试用例

总结与反思

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