题解：SP32899 MEANARR - Mean of array

· · 题解

前言

又到了喜闻乐见的 SPOJ 水题解大时间，蒟蒻翻了整整三天，终于翻到了这道在蒟蒻水平范围内的题目，于是光速发了题解，吐槽一下本题基本什么也没有，从数据范围到标签全部都是未补全的情况。

题目大意

给定一个有 n 个元素的序列，让你求满足区间平均值大于等于 k 的区间个数。

分析

首先肯定是给出满足条件区间的式子（下面的公式中用 sum 表示原序列的前缀和数组）：

\frac{sum_{r}-sum_{l-1}}{r-l+1}\geq k

进一步化为：

k \times (r-l+1) \leq sum_{r}-sum_{l-1}

发现其中的 k 不好直接处理，考虑将其消除，具体体现为将原序列中每个数减去 k 即可，之后便转化为：

sum_{r}-sum_{l-1}\geq 0

即

sum_{r} \geq sum_{l-1}

于是问题转化为：给定一个长为 n 的序列，将序列中的每个元素均减去 k 之后，求当前序列的前缀和数组 sum 中有多少合法的 l 和 r 满足 sum_{r} \geq sum_{l-1}。

这是一个明显的二维偏序问题，考虑用树状数组求解。

实现

根据分析中提到的方法，将每个元素都减去 k 后的原序列进行前缀和计算，将每个前缀和当做树状数组中的点，将这些点的值设为 1，这样在查询时就可以用树状数组带有的前缀和功能求出有多少个比当前值小或等于的数，再统计答案即可，其中需要注意要单独统计 l=1 的情况。

代码

下面给出代码，注意需要开 long long，且注意对前缀和数组进行离散化后再存点。

#include <bits/stdc++.h>
#define ll long long
#define copy ada
#define int long long
#define lowbit(x) x&-x
#define rsort(a) sort(a+1,a+n+1),reverse(a+1,a+n+1)
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
using namespace std;
const int N=7e5+10;
int n,k,a[N],sum[N],ans,copy[N],m;
struct b1t{//树状数组
    int c[N];
    void add(int x,int val){
        for(;x<=n;x+=lowbit(x)){
            c[x]+=val;
        }
    }
    int q(int x){
        int ret=0;
        for(;x;x-=lowbit(x)){
            ret+=c[x];
        }
        return ret;
    }
}tr;
int get_rank(int x){
    return lower_bound(copy+1,copy+m+1,x)-copy;
}
signed main() {
    IOS
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]-=k;
        sum[i]=sum[i-1]+a[i];
        copy[i]=sum[i];
        if(sum[i]>=0)ans++;    
    }
    sort(copy+1,copy+n+1);//离散化
    m=unique(copy+1,copy+n+1)-(copy+1);
    for(int i=1;i<=n;i++){
        int rank=get_rank(sum[i]);
        ans+=tr.q(rank);//统计答案
        tr.add(rank,1);//加点
    }
    cout<<ans;
    return 0;
}