题解 | 有趣的区间

根据二进制按位或的性质，我们不难发现"有趣的区间"就是至少包括一个奇数的区间。

我们考虑枚举数组A下标i从1~n，枚举的时候我们只统计以当前下标为区间右端点的答案。（可以证明，这样统计是不重不漏的）

如果当前枚举的数A[i]是奇数，那么所有区间[j,i]，j取遍1~i，都是"有趣的区间"，对答案的贡献+i；

如果当前枚举的数A[i]是偶数：

若此前没有出现过奇数，那么以当前下标为右端点的区间都不是"有趣的区间"，对答案没有贡献；

若此前出现过奇数，且最近一次出现奇数的位置为lastOddIdx，那么对于区间[j,i]，j取遍1~lastOddIdx，都为"有趣的区间"，对答案贡献+lastOddIdx。

综上，我们需要在枚举A[i]时维护一个最近一次出现奇数的位置lastOddIdx，在枚举A[i]时按上述条件判断累加答案，最后输出答案即可，答案可能爆int，因此答案需要开long long。时间复杂度为O(n)，不会超时。

#include <iostream>
#include <vector>

using i64 = long long;

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

  int n;
  std::cin >> n;

  std::vector<int> A(n+1);
  for(int i = 1; i <= n; i++){
    std::cin >> A[i];
  }

  i64 ans = 0;
  int lastOddIdx = -1;

  for(int i = 1; i <= n; i++){
    if(A[i] & 1){
      lastOddIdx = i;
      ans += i;
    }else if(~lastOddIdx){
      ans += lastOddIdx;
    }
  }

  std::cout << ans << "\n";
}