1. 问题分析

问题的核心在于只要区间 内所有元素进行按位或（Bitwise OR）运算后的结果为奇数，该区间即被视为“有趣”。

  • 位运算性质：整数的奇偶性仅由二进制表示的最低有效位（LSB, Least Significant Bit，即第0位）决定。
    • 若第0位为1，则数为奇数。
    • 若第0位为0，则数为偶数。
  • 或运算（OR）特性：对于运算 ，只要 和 中至少有一个数的第0位为1，结果 的第0位即为1。推广到区间， 为奇数的充要条件是：区间 中至少存在一个奇数。
  • 反向条件：区间“不有趣”（即结果为偶数）的充要条件是：区间 中所有元素均为偶数。
  • 暴力枚举：，不可行。

2. 算法：补集计数法 (Complementary Counting)

对于“至少存在一个”这类存在性问题，直接计数通常涉及复杂的去重逻辑或单调性维护。正难则反，采用补集思想由全集减去不满足条件的集合，是解决此类问题的最优范式。

  1. 全集计算：数组 的所有可能连续子区间总数为 。
  2. 补集定义：寻找所有“全偶区间”。即寻找原数组中由连续偶数构成的最大连通分量（Connected Components）。
  3. 分块计算：假设原数组中有一段连续的偶数序列长度为 （例如 [奇, 偶, 偶, 偶, 奇]，中间连续偶数长度 ）。这段偶数序列内部能够形成的“不有趣区间”个数为 。
  4. 最终计算：

3. 复杂度

时间复杂度：

  • 算法仅需对数组进一次线性扫描（One Pass），识别连续偶数段的长度。

空间复杂度：

  • 仅需常数个变量存储当前连续偶数的长度、总计数等。不需要额外的数组或复杂数据结构。

4. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    ll n;
    cin >> n;

    ll total = n * (n + 1) / 2LL;
    ll even = 0LL;
    ll invalid = 0LL;

    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        if (a % 2 == 0) {
            even++;
        } else {
            invalid += even * (even + 1) / 2LL;
            even = 0LL;
        }
    }
    if (even > 0) {
        invalid += even * (even + 1) / 2LL;
    }
    ll ans = total - invalid;
    cout << ans << endl;
}