前缀和

我们使用前缀和思想用一个数组来记录序列[1,i]当中负数的个数，然后再用两个数组分别来记录[1,i]当中这个负数个数为奇的下标的个数，和[1,i]当中这个负数个数为偶的下标的个数
我们在分析一个下标作为r下标的情况的时候，可以让这个[l,r]序列为负的方法只有当[l,r]这个序列当中负数个数为奇才行，那么我们可以分析如果[1,r]的负数个数为奇数，那么我们只要找出在[1,r)当中负数个数为偶数的下标的个数，我们就可以让c1加上这个个数。
这里要注意的一点是：当[1,i]的负数个数为奇数时，我们以r为结尾下标，上面只算到了左下标l为[1,i-1]的情况，忽略了我们可以让i也作为左下标的可能性，所以我们在计算cnt[i]为奇的情况的时候，c1+=cnt2[i-1]+1
同样的，如果[1,r]的负数个数为偶数，那么我们只要找出在[1,r)当中负数个数为奇数的下标的个数，我们就可以让c1加上这个个数。最后我们知道所有的序列组合数和肯定是(n+1)n/2，且每一种组合的情况是非此即彼的，那么c2=(n+1)n/2-c1;
出

code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5*100010;
long long n;
long long a[N],cnt[N],cnt1[N],cnt2[N];
long long c1,c2;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        cnt[i]=cnt[i-1];
        if(a[i]<0)cnt[i]++;
    }
    for(int i=1;i<=n;i++)
    {
        cnt1[i]=cnt1[i-1];
        cnt2[i]=cnt2[i-1];
        if(cnt[i]%2)cnt1[i]++;
        else cnt2[i]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(cnt[i]%2)
        {
            c1+=cnt2[i-1]+1;
        }
        else
        {
            c1+=cnt1[i-1];
        }
    }
    c2=(n+1)*n/2-c1;
    cout<<c1<<" "<<c2;
    return 0;

}