[Codeforces 1058E] Vasya and Good Sequences

[题目链接]

https://codeforces.com/contest/1058/problem/E

[算法]

显然 ， 我们只需考虑序列中每个数的二进制表示下1的个数即可。 不妨令Ai表示第i个数的二进制表示下1的个数。

一个子序列[L,R]是“好”的当且仅当 ：

1. sigma{ Ai }  (L <= i <= R) 为偶数

2. max{ Ai } (L <= i <= R) <= sigma{ Ai } / 2

枚举序列左端点L ， 可以用后缀和处理R

时间复杂度 ：O(N)

[代码]

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 3e5 + ;

int n;

int cnt[MAXN][];

int a[MAXN];

long long ans;

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

int main()

{

        read(n);

        for (int i = ; i <= n; i++)

        {

                long long x;

                read(x);

                while (x > )

                {

                        a[i] += x & ;

                        x >>= ;

                }

        }

        int suf = ;

        cnt[n + ][] = ;

        for (int i = n; i >= ; i--)

        {

                int sum =  , mx = ;

                int add = ;

                for (int j = i; j <= n && j - i < ; j++)

                {

                        sum += a[j];

                        mx = max(mx,a[j]);

                        if (sum %  ==  && mx > sum - mx) add--;

                }

                suf += a[i];

                add += cnt[i + ][suf & ];

                ans += add;

                cnt[i][] = cnt[i + ][];

                cnt[i][] = cnt[i + ][];

                if (suf & ) cnt[i][]++;

                else cnt[i][]++;

        }

        printf("%I64d\n",ans);

        return ;

}