一道神题

—恢复内容开始—

给一个长为N的序列，对与一个区间，如果其平均值在【L,R】内，你比较厉害。

求你比较厉害的概率。

我只做了35分，但看了别人的神代码，我终于领会到了代码的神奇。

思路：

　　我们先求平均值在【0，R】，和【0，l）的区间个数。

　　令a[i]=a[i]-R;　　s[i]为a[i]的前i项的和，那么s[i]的增减就代表了 某个区间，是否是厉害区间。（增代表不是,减或者连续的减，都代表了这一段区间是厉害区间）

　　然后查找逆序对的个数，因为区间平均值的 值域是很小的 对于每个值都有 很多的重复，这就用到了离散化（因为只需要知道其相对位置就行了）。

　　　　这里用到了unque去重函数

　　

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long 
#define N 500010
LL n,l,r;
LL ans1,ans2,a[N],b1[N],b2[N],c[N],t,ans,tot;
LL s1[N],s2[N];
#define lowbiti) i&-i))
void gcd)
{
    long long a,b,c;
    a=ans,b=tot;
    whileb)
    {
        c=a%b;
        a=b;
        b=c;
    }
    t=a;
}
void Addint x)
{
    forint i=x;i<=n;i+=lowbiti))        c[i]++;
}
LL Getint x)
{
    LL ans=0;
    forint i=x;i>=1;i-=lowbiti))
        ans+=c[i];
    return ans;
}
int main)
{
    freopen"jian.in","r",stdin);
    freopen"jian.out","w",stdout);
    scanf"%d%d%d",&n,&l,&r);
    forint i=1;i<=n;i++)    
        scanf"%d",&a[i]);
    forint i=1;i<=n;i++)
    {
        s1[i]=s1[i-1]+a[i]-l;
        b1[i]=s1[i];
        ifs1[i]<0) ans1++;
        s2[i]=s2[i-1]+a[i]-r;
        b2[i]=s2[i];
        ifs2[i]<=0)    ans2++;
    }
    
    sorts1+1,s1+1+n);
    sorts2+1,s2+n+1);
    LL t1=uniques1+1,s1+1+n)-s1-1;
    LL t2=uniques2+1,s2+1+n)-s2-1;
    forint i=1;i<=n;i++)
    {
        LL pos=lower_bounds1+1,s1+1+t1,b1[i])-s1;
        b1[i]=pos;
        pos=lower_bounds2+1,s2+1+t2,b2[i])-s2;
        b2[i]=pos;
    }
    forint i=n;i>=1;i--)
    {
        ans1+=Getb1[i]);
        Addb1[i]+1);
    }
    memsetc,0,sizeof c);
    forint i=n;i>=1;i--)
    {
        ans2+=Getb2[i]);
        Addb2[i]);
    }
    ans=ans2-ans1; 
    tot=n+1)*n/2;
    ifans==tot)
    {
        cout<<1;
        return 0;
    } 
    ifans==0)
    {
        cout<<0;
        return 0;
    }
    gcd);
    printf"%lld/%lld",ans/t,tot/t);
    return 0;
}

—恢复内容结束—