题解 P2804 【神秘数字】

· · 题解

思考当前问题

我们得到数列a，要求多少个区间的和平均数大于m

那么我们把数列a每一个数减去m 得到数列A

那么如果数列A中某个区间的和如果大于0，原数列a中这个区间的平均数就大于m（这个还是好想的，平均数大于m，那么和就大于m乘以区间长度）

问题转化为求当前数列A中有多少个区间的和大于0

继续思考

我们求出A数列的前缀和数列S

那么一个区间A[i]...Aj的和大于0的要求就是

S[j]-S[i-1]>0

也就是

S[j]>s[i-1]

至此，问题已经非常清晰了

问题转化为求S[j]之前有多少个S[i]>S[j],把相对于每一个S[j]的答案个数相加就是ans

也就是求前缀和数列S的逆序对

注意 要追加S[0]=0,因为这个代表从开头开始的一个区间也要计算(否则会少算一些答案)

下面贴出归并排序求逆序对的代码 期望复杂度O(nlogn)

楼主上大学了 多年没上洛谷 看到这题评论区里有讨论关于顺逆序的问题 楼主的意思是 ”顺“ “逆” 是对于这个“序”而言的 可以认为是升序的顺序对，也可以理解是降序的逆序对

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int a[200010],sum[200010],ans,temp[200010];
//sum为前缀和
int n,m;
int merge(int l,int mid,int r){
    int p1=l,p2=mid+1,k=l-1;
    while(p1<=mid&&p2<=r){
        if(sum[p1]<sum[p2]){
            ans+=(mid-p1+1);
            ans%=92084931;
            temp[++k]=sum[p2];
            p2++;
        }
        else if(sum[p1]>=sum[p2]){
            temp[++k]=sum[p1];
            p1++;
        }
    }
    while(p1<=mid) temp[++k]=sum[p1++];
    while(p2<=r) temp[++k]=sum[p2++];
    for(int i=l;i<=r;i++)
        sum[i]=temp[i];
}
void mergesort(int l,int r){
    if(l<r){
        int mid=(l+r)>>1;
        mergesort(l,mid);
        mergesort(mid+1,r);
        merge(l,mid,r);
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[i]-=m;
        sum[i]=sum[i-1]+a[i];
    }
    mergesort(0,n);
    printf("%d\n",ans);
    return 0;
}