感觉题解的办法好简单呜呜呜，但是我不会。

这里给出我的做法：

由题意知，只要区间中有一个数为奇数那么该区间就是有趣的区间。
不妨考虑[1,n]的所有区间个数设为s，不管它是否有趣。
那么显然s = (1+n)*n/2

考虑以下例子：

5
1 2 3 4 5

那么列出所有区间就是

(1,1) (1,2) (1,3) (1,4) (1,5)
(2,2) (2,3) (2,4) (2,5)
(3,3) (3,4) (3,5)
(4,4) (4,5)
(5,5)

观察可知有趣区间是：

(1,1) (1,2) (1,3) (1,4) (1,5) 
(2,3) (2,4) (2,5)
(3,3) (3,4) (3,5)
(4,5)
(5,5)

那么可以首先

1. 然后只需要枚举每个数字 判断奇偶性 
2. 如果当前数字为奇数，那么从该数字开始的所有区间都是有趣的区间，贡献是n-i+1
3. 如果当前数字为偶数，那么要从该数字开始寻找第一次出现的奇数，假设找到的奇数序号是j,那么贡献是n-j+1

很容易写出关键代码：

    ll sum = 0;
    for(ll i = 1;i<=n;i++)
    {
        if(a[i]%2==1)
        {
            sum+=n-i+1;continue;
        }
        else
        {
            ll j = i;
            while(a[j]%2==0&&j<n)
            {//寻找第一次出现的奇数
                j++;
            }
    		sum+=n-j+1;
        }
    }

但是这样的话会超时，观察知数据范围5e5,而这个算法双重循环时间复杂度为O(n^2),评测机一般1s是1e7~1e8，那么显然会超时，再观察代码知，当

a[i]%2==0时，从i到第一次奇数出现的序号j之间，是没有必要枚举的，所以可以双指针优化，每一次找到j后，令i = j，然后时间复杂度就是O(n)，就可以AC啦！

ACcode：

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

typedef long long ll;
ll sum;
const int N = 5e5+10;
ll a[N];
int n;
int main()
{
    cin>>n;
    for(ll i = 1;i<=n;i++)
    {
        cin>>a[i];
    }
    ll sum = 0;
    for(ll i = 1;i<=n;i++)
    {
        if(a[i]%2==1)
        {
            sum+=n-i+1;continue;
        }
        else
        {
            ll j = i;
            while(a[j]%2==0&&j<n)
            {
                j++;
            }
            if(j<n)
            {
                sum+=n-j+1;continue;
            }
            if(a[j]%2!=0)
            {
                sum+=j-i+1;
            }
            i = j;
        }
    }
    cout<<sum;
}

题解 | #小白月赛43 D.有趣的区间#

感觉题解的办法好简单呜呜呜，但是我不会。