题解 | #有趣的区间#

Problem

Solution

翻译下题意：当一个区间内存在一个元素为奇数时，则被称为有趣的区间，并且只要两个区间的左右端点有一个不一样，这两个区间就不是同一个区间。
了解题意后，如何求出满足条件的区间个数呢？
我们可以假设数组内所有元素都为奇数，可以很容易地想到，此时的区间个数为1 + 2 + 3 + ... + n。
由此可以看出，我们可以很轻易地求出所有区间数，又因为不满足的区间数为1 + 2 + 3 + ... k(奇数区间的长度)。
所以有趣的区间数 = 所有区间数 - 不满足的区间数。
我们只需要依次找到每个不含奇数的区间长度即可。

Code

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long ll;
const int N = 5e5 + 7;

int a[N];
ll n;

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] & 1) a[i] = 1;  // 标记元素为奇数
        else a[i] = 0;  // 标记元素为偶数
    }
    
    long long res = n * (n + 1) / 2;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 0)  // 找到偶数区间
        {
            int k = 1;
            res -= k;
            i++;
            while (i <= n && a[i] == 0)
            {
                k++;
                res -= k;
                i++;
            }
            i--;
        }
    }
    cout << res << endl;
    return 0;
}