题目描述

题目大意：统计这个数组有多少个乘积是正数的子区间和乘积是负数的子区间

算法

树状数组 $O(nlogn)$

一开始只想打暴力。
暴力的做法是统计前缀和负数的个数。
区间内负数个数为偶数乘积是正数
区间负数个数为奇数数乘积是负数
枚举区间区间就完事了。
但是这样不行。
换个思路枚举区间左端点，右端点。
发现右端点为i的区间由0~i-1中得来
于是右端点sum为奇数那么找只需要统计左端点的sum偶数(奇数)个数就获得负数(正数)的个数了。
这个可以1~i的前缀和可以由树状数组统计.

时间复杂度

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+100;
int c[2][N];
int n;
int lowbit(int x){return x&-x;}
void add(int k,int x){
    for(;x<=n;x+=lowbit(x)){
        c[k][x]++;
    }
}

int query(int k,int x){
    int res=0;
    for(;x;x-=lowbit(x)) res+=c[k][x];
    return res;
}

#define ll long long
int sum[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        sum[i]=sum[i-1]+(x<0); //统计负数的个数
    }
    ll ans1=0,ans2=0;
    for(int i=1;i<=n;i++){
        int a=query(0,i-1);
        int b=query(1,i-1);
        if(sum[i]%2==1) { 
            ans1++;//0~i的负数个数为奇数
            ans1+=b;
            ans2+=a;
            add(0,i);
        }
        else{
            ans2++;//0~i的负数个数为偶数
            ans1+=a;
            ans2+=b;
            add(1,i);
        }
    }
    cout<<ans1<<" "<<ans2<<endl;
    return 0;
}