【NOIP模拟】区间平均值

这篇文章上次修改于 574 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

本文共 2264 个字，阅读时长 ≈ 6 分钟

题意

输入 $N, l, r$ 并给你 N 个数，随机选取区间，如果所选区间的平均数 x 满足 $l \leq x \leq r$ 就称这个区间为牛逼的，问所有选取区间的方案中选中牛逼区间的概率为多少。

思路

这题思路不大好想，先考虑暴力。30分的暴力可以直接 $O (n^{2})$ 枚举区间，用前缀和算平均数，统计答案即可。60分的不会（）那该怎么把暴力搞成个正解呢？我们也许可以想到，求区间平均数 $x \in [l, r]$ 的区间个数可以通过求区间平均数 $x \in [1, r] - x \in [1, l)$ 算出来，那这样的话我们需要维护两个地方， $x \in [1, l)$ 和 $x \in [1, r]$ 。

这里有一个应该是套路的东西吧，求区间平均数 $x \leq a$ 的区间个数，我们可以将这个区间每个元素都减去 $a$ 并相加，如果最终的和 $\leq 0$ ，那这个区间平均数就满足 $x \leq a$ 。为什么呢？让我们来证一下。

设区间长度为 $l$ ，区间平均数为 $x$ ，区间和为 $s u m$

$\begin{matrix} ∵ x = \frac{s u m}{l} \\ ∴ s u m = l \times x \\ ∴ s u m - l \times a = l \times x - l \times a = l \times (x - a) \\ if l \times (x - a) \leq 0 \\ ∵ l > 0 \\ ∴ x - a \leq 0 \\ ∴ x \leq a \end{matrix}$

证毕撒花~

那么就是对于已经减完的数组求个前缀和，如果 $s u m [k] - s u m [i - 1] \leq 0$ 也就是 $s u m [k] \leq s u m [i - 1]$ 时这个区间是满足条件的。又因为 $k > i - 1 & s u m [k] \leq s u m [i - 1]$ 我们很难不想到逆序对这个东西，那就好做啦，直接求逆序对个数即可。

然后总共做两次操作，一次是减去 $l$ ，另一次是减去 $r$ 。最后要注意的一点就是第一个区间 $[1, l)$ 是左闭右开，所以要严格大于的逆序对，这里直接在query时减1即可；而第二个区间 $[1, r]$ 是左闭右闭，不需要严格大于。

如果你用树状数组求逆序对的话，要注意因为前缀和有可能为负数，树状数组又是在值域上开的，所以要简单离散化一下，防止下标爆炸。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define int long long
#ifdef ONLINE_JUDGE
#define debug(x)
#else
#define debug(x) cout<<' '<<#x<<'='<<x<<endl
#endif
using namespace std;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=1000006;
int n,l,r,c1,c2;
int a[N],b[N],c[N],bit[N],s1[N],s2[N];
//以下为树状数组求逆序对
inline int lb(int x){return x&(-x);}
inline void add(int x){
    while(x<=n){
        bit[x]++;
        x+=lb(x);
    }
}
inline int query(int x){
    int res=0;
    while(x){
        res+=bit[x];
        x-=lb(x);
    }
    return res;
}
signed main()
{
    // freopen("niu.in","r",stdin);
    // freopen("niu.out","w",stdout);
    n=read();
    l=read(); r=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        //分别求出-l和-r的前缀和
        s1[i]=a[i]-r+s1[i-1];
        s2[i]=a[i]-l+s2[i-1];
        //离散化数组
        b[i]=s1[i]; c[i]=s2[i];
        //这里先统计一下
        if(s1[i]<=0) ++c1;
        if(s2[i]<0) ++c2;
    }
    //离散化
    sort(b+1,b+1+n);
    sort(c+1,c+1+n);
    int m1=unique(b+1,b+1+n)-b-1,m2=unique(c+1,c+1+n)-c-1;
    for(int i=1;i<=n;++i){
        s1[i]=lower_bound(b+1,b+m1+1,s1[i])-b;
        s2[i]=lower_bound(c+1,c+m2+1,s2[i])-c;
    }
    //求逆序对个数
    for(int i=n;i;i--){
        c1+=query(s1[i]);
        add(s1[i]);
    }
    memset(bit,0,sizeof(bit));
    for(int i=n;i;i--){
        c2+=query(s2[i]-1);
        add(s2[i]);
    }
    //计算概率输出答案
    int ans=c1-c2,nn=(n+1)*n/2;
    int d=__gcd(ans,nn);
    if(ans==nn) printf("1");
    else if(ans==0) printf("0");
    else printf("%lld/%lld",ans/d,nn/d);
    return 0;
}