P2309 loidc,卖卖萌 题解

· · 题解

题目简述

题目分析

假设 s_i 为前缀和，本题即求有多少对 (l,r) 使得：

l<r,s_l<s_r

这显然是正序对个数，直接归并求解即可（如果不会逆序对的同学可以点这里）。

代码

#include<iostream>
using namespace std;
#define ll long long
const int MAXN=1e5+5;
int n,a;
int s[MAXN];
int t[MAXN];
ll ans=0;
void msort(int l,int r){
    if(l==r)
        return;
    int mid=(l+r)/2;
    msort(l,mid);
    msort(mid+1,r);
    int p=l,q=mid+1,k=l;
    while(p<=mid&&q<=r){
        if(s[p]>=s[q])
            t[k++]=s[q++]; 
        else
            t[k++]=s[p++],ans+=r-q+1;
    }
    while(p<=mid)
        t[k++]=s[p++];
    while(q<=r)
        t[k++]=s[q++];
    for(int i=l;i<=r;i++)
        s[i]=t[i];
    return; 
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        s[i]=s[i-1]+a;
    }
    msort(0,n);
    //for(int i=1;i<=n;i++)
    //  cout<<s[i]<<" ";
    cout<<ans;
}