codevs 1516 平均分数

题目描述 Description
X学校被抽中进行一次数学测验，该学校共有N人，每个人有一个学号，一号学生的学号是1…N号学生的学号是N.
为了减轻统计的负担，该学校只会随机抽取学号连续的k人(1≤k≤n)，且将该k人的平均分统计出来。小明已经知道了所有人的成绩，小明想知道，平均分在[L,R]上的概率为多少。
输入描述 Input Description
输入共2行。
第一行为三个正整数，N,L,R.
第二行第i个数为学号为i的学生的成绩。
输出描述 Output Description
输出学生的分数,表示成既约分数。

记sum[i]为前缀和。则需求满足
L<=(sum[i]-sum[j])/(i-j)<=R (j<i)
的数对个数。
对于L<=(sum[i]-sum[j])/(i-j) 变形有：
Li-sum[i]<=Lj-sum[j] (j<i)
令Ai=Li-sum[i]; 统计非严格逆序对个数cntA，得到有多少数对的平均值大于等于L。
对于(sum[i]-sum[j])/(i-j)<=R 我们考虑求出(sum[i]-sum[j])/(i-j)>R，变形有：
Ri-sum[i]<Rj-sum[j] (j<i)
令Bi=Ri-sum[i]，统计严格逆序对cntB，得到有多少数对的平均值大于R。
cntA为满足大于L的数对个数，cntB为满足大于R的数对个数
两数相减，即为满足大于L又小于R的数对个数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
long long xl[1245000],sum[1245000];
long long a[1245000],b[1245000];
long long ans1,ans2;
long long temp[1245000];
void merge_sort1(long long l,long long r){
    if(l==r){
        return ;
    }
    long long mid=(l+r)/2;
    merge_sort1(l,mid);
    merge_sort1(mid+1,r);
    long long s=l,t=mid+1,p=l;
    while(s<=mid&&t<=r){
        if(a[s]<a[t]){
            temp[p++]=a[s];
            s++;
        }
        if(a[s]>=a[t]){
            temp[p++]=a[t];
            ans1+=mid-s+1;
            t++;
        }
    }
    while(s<=mid){
        temp[p++]=a[s];
        s++;
    }
    while(t<=r){
        temp[p++]=a[t];
        t++;
    }
    for(long long i=l;i<=r;i++){
        a[i]=temp[i];
    }
}
void merge_sort2(long long l,long long r){
    if(l==r){
        return ;
    }
    long long mid=(l+r)/2;
    merge_sort2(l,mid);
    merge_sort2(mid+1,r);
    long long s=l,t=mid+1,p=l;
    while(s<=mid&&t<=r){
        if(b[s]<=b[t]){
            temp[p++]=b[s];
            s++;
        }
        if(b[s]>b[t]){
            temp[p++]=b[t];
            ans2+=mid-s+1;
            t++;
        }
    }
    while(s<=mid){
        temp[p++]=b[s];
        s++;
    }
    while(t<=r){
        temp[p++]=b[t];
        t++;
    }
    for(long long i=l;i<=r;i++){
        b[i]=temp[i];
    }
}
long long gcd(long long a,long long b){
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}
int main()
{
    long long n,l,r;
    cin>>n>>l>>r;
    for(long long i=1;i<=n;i++){
        scanf("%lld",&xl[i]);
        sum[i]=xl[i]+sum[i-1];
        a[i]=l*i-sum[i];
        b[i]=r*i-sum[i];
    }
    /*for(long long i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }*/
    merge_sort1(0,n);
    merge_sort2(0,n);
    /*for(long long i=1;i<=n;i++){
        if(xl[i]>=l){
            ans1++;
        }
        if(xl[i]>r){
            ans2++;
        }
    }*/
    long long acount=(n+1)*n/2;
    //cout<<ans1<<" "<<ans2<<endl;
    long long ans=ans1-ans2;
    if(ans%acount==0){
        cout<<ans/acount<<endl;
    }
    else{
        long long m=gcd(ans,acount);
        cout<<ans/m<<"/"<<acount/m<<endl;
    }
    return 0;
}