Qbxt 模拟题 day2(am) T2 jian

【问题描述】

有N个数，随机选择一段区间，如果这段区间的所有数的平均值在[L,R]中则你比较厉害。求你比较厉害的概率。

【输入格式】

第一行有三个数N, l, r，含义如上描述。

接下来一行有N个数代表每一个数的值。

【输出格式】

输出一行一个分数a/b代表答案，其中a, b互质。如果答案为整数则直接输出该

整数即可。

【样例输入 1】

4 2 3

3 1 2 4

【样例输出 1】

7/10

【样例输入 2】

4 1 4

3 1 2 4

【样例输出 2】

1

【样例解释】

塔外面有棵树。

【数据规模与约定】

对于30%的数据， 1 ≤ N ≤ 104。

对于60%的数据， 1 ≤ N ≤ 105。

对于100%的数据， 1 ≤ N ≤ 5 × 105, 0 < l ≤ r ≤ 100。

/*

要求区间平均值∈[L,R]的区间个数

现在我们来求区间平均值在1~r的个数和1~l(不包括l)的个数 前减后即为所求

以求1~r为例（用[L,R]-[1,L））

(a[i]+a[i+1]+......+a[i+k-1])/k<=r

[(a[i]+a[i+1]+......+a[i+k-1])+kr]/k<=0

[(a[i]-r)+(a[i+1]-r)+......+(a[i+k-1]-r)]/k<=0 (k>0)

so (a[i]-r)+(a[i+1]-r)+......+(a[i+k-1]-r)<=0

令s[i]=∑(a[i]-r)

即求s数组区间和<=0的个数

s[i+k-1]-s[i]<=0

s[i+k-1]<=s[i]

i<i+k-1

s[i]>=s[i+k-1]

即求s数组逆序对数.

答案为(ansr-ansl)/(n*(n+1)/2）.

法二:要求[L,R]的合法答案只需求出不合法答案算补集.

合法的是>=l的正序对个数和<=r的逆序对个数.

so 只需求>=l的逆序对个数和<=r的正序对个数不合法即可(两者必定无交集).

(求正序对只需翻转数组即可orz.)

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 500001

#define LL long long

using namespace std;

LL n,l,r,ansl,ansr,tot,a[MAXN],b[MAXN],b1[MAXN],tot1;

struct data{LL x,o;}s[MAXN],c[MAXN];

LL read()

{

    LL x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

bool cmp(const data &x,const data &y)

{

    return x.x<y.x;

}

void add(LL x)

{

    while(x<=n)

    a[x]++,x+=x&-x;

    return ;

}

LL query(LL x)

{

    LL sum=0;

    while(x>0) sum+=a[x],x-=x&-x;

    return sum;

}

int main()

{

    freopen("jian.in","r",stdin);

    freopen("jian.out","w",stdout);

    LL x;

    n=read(),l=read(),r=read();

    for(LL i=1;i<=n;i++) x=read(),c[i].o=s[i].o=i,

    c[i].x=c[i-1].x+x-l,s[i].x=s[i-1].x+x-r;

    sort(c+1,c+n+1,cmp),sort(s+1,s+n+1,cmp);

    b[c[1].o]=1,b1[s[1].o]=1;

    if(c[1].x<0) ansl++;

    if(s[1].x<=0) ansr++;

    for(LL i=2;i<=n;i++)

    {

        if(c[i].x==c[i-1].x) b[c[i].o]=b[c[i-1].o];

        else b[c[i].o]=b[c[i-1].o]+1;

        if(s[i].x==s[i-1].x) b1[s[i].o]=b1[s[i-1].o];

        else b1[s[i].o]=b1[s[i-1].o]+1;

        if(c[i].x<0) ansl++;

        if(s[i].x<=0) ansr++;

    }

    for(LL i=n;i>=1;i--) ansl+=query(b[i]),add(b[i]+1);

    memset(a,0,sizeof a);

    for(LL i=n;i>=1;i--) ansr+=query(b1[i]),add(b1[i]);

    LL ans=ansr-ansl,total=n*(n+1)/2;

    LL xx=__gcd(ans,total);

    ans/=xx,total/=xx;

    if(total==1) cout<<ans;

    else cout<<ans<<'/'<<total;

    return 0;

}

巴特西

Qbxt 模拟题 day2(am) T2 jian

最新文章

热门文章