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;}

测试用例

输入	输出	说明
n=3, a=[1,2,4]	4	总区间 6，全偶区间 2
n=4, a=[2,4,6,8]	0	全偶，全部扣除
n=5, a=[1,3,5,7,9]	15	无全偶区间，等于总数

---

总结与反思

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