题解 | 有趣的区间（C++）

这道题看似跟按位或有关系，实际上并没有hhh，小误导

依据题目定义，一个奇数与一个奇数或者偶数“|”运算后都会得到奇数，只有两个偶数“|”运算后会得到偶数；而按位或运算遵从交换律，那么我们翻译一下题目，也就是说，只要一个区间内有奇数，那么这个区间就满足题目条件

我们在输入完数据以后可以分开进行思考，从头到尾进行遍历的时候，如果a[i]是奇数，那么区间[i,i]一直到区间[i,n]都是合法答案，累计n - i + 1个；而如果a[i]是偶数，那我们就要向后找直到找到一个奇数,假设是a[j]，那么发现区间[i,j]一直到区间[i,n]都是合法答案，累计n - j + 1个。

那么不难发现，我们可以设置一个计数器k，每次遍历到偶数a[i]时，让k加1；而每次遍历到奇数a[i]时，前面就有k个待处理的偶数a[x],[x,i]构成满足要求的最小区间，同时再考虑奇数a[i]自身的情况，所以答案一共加上(k + 1) * (n - i + 1)，然后记得把计数器k清零。

最后就得到答案啦，算法时间复杂度O(n)，满足题目条件（记得看数据量是5e5，我就是没看到数据量在那看了半天没发现错哪hh）

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
// #define int long long
// #define ctz __builtin_ctzll  // 不 define int long long记得删
// #define clz __builtin_clzll  // 不 define int long long记得删
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 2e6 + 10;
const ll MOD = 1e9 + 7; // 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll a[N];

void LiangBaiKai()
{

}

void Aiden()
{
    ll m, n, sum = 0, ans = 0, num = 0, i, j, k, mi = INF, ma = -INF, cnt = 0, x, y, len, t, l, r;
    cin >> n;
    k = 0;
    for (i = 1; i <= n;i++)
        cin >> a[i];
    for (i = 1; i <= n;i++)
    {
        if (a[i] & 1)
        {
            ans += (k + 1) * (n - i + 1);
            k = 0;
        }
        else
            k++;
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //LiangBaiKai();
    int _ = 1;
    //cin >> _;
    while (_--)
        Aiden();
    return 0;
}