【问题描述】

有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<=10⁴ 。

60%的数据，1 ≤N≤ 10 ⁵ 。

对于100%的数据，1 ≤ N≤ 5× 10 ⁵ ,0 < L ≤ R ≤ 100。

 

______________________________________________________________________

很神奇的数学题，难在推公式，并把公式和信息学的东西联系起来。这是信息题吗？算是数学信息题吧！！！

推理过程：

1、求区间平均值在【l,r】间的概率

2、求平均值在[l,r]间的个数，在除以n(n+1)就可以了

3、[l,r]间的个数=小于等于r的个数-小于l的个数

4、小于l可以表示为（ａ［ｉ］＋ａ［ｉ＋１］＋ａ［ｉ＋２］＋……+a[i+k-1]）/k<l

　　继续推出（ａ［ｉ］＋ａ［ｉ＋１］＋ａ［ｉ＋２］＋……+a[i+k-1]）<l*k

　　再推出（ａ［ｉ］＋ａ［ｉ＋１］＋ａ［ｉ＋２］＋……+a[i+k-1]）-l*k<0

　　再再推出（ａ［ｉ］-l＋ａ［ｉ＋１］-l＋ａ［ｉ＋２］-l＋……+a[i+k-1]-l）<0

　　让数组b[i]=a[i]-l;

　　公式变为b［ｉ］＋b［ｉ＋１］＋b［ｉ＋２］＋……+b[i+k-1]<0

　　用前缀和维护可得：s[i+k-1]-s[i-1]<0;

　　这是什么？逆序对！！！逆序对的个数就是小于l的个数

　　同理求出小于等于r的个数。差，OK!

　　神啊！再让我做一遍，我还是做不出来！！！

______________________________________________________________________

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5   6 using namespace std;  7 long long n,l,r,ans1,ans2;  8 long long a[500010],b[500010],c[500010],d[500010];  9 void readlong(long long &x) 10 { 11     char c=getchar(); 12     int fh=1; 13     for(;c>'9'||c<'0';c=getchar())if(c=='-')fh*=-1; 14     x=0; 15     for(;c<='9'&&c>='0';c=getchar())x=x*10+c-'0'; 16     x=x*fh; 17 } 18  19 void nxd1(long long l,long long r) 20 { 21     if(l==r)return; 22     long long mid=(l+r)/2; 23     nxd1(l,mid);nxd1(mid+1,r); 24     long long z=l,y=mid+1,x=l; 25     while(z<=mid&&y<=r) 26     { 27         if(b[z]>b[y]) 28         { 29             ans1+=mid-z+1; 30             d[x++]=b[y];y++; 31         } 32         else 33         { 34             d[x++]=b[z];z++; 35         } 36     } 37     while(z<=mid) 38     { 39         d[x++]=b[z];z++; 40     } 41     while(y<=r) 42     { 43         d[x++]=b[y];y++; 44     } 45     memcpy(b+l,d+l,(r-l+1)*8); 46 } 47 void nxd2(long long l,long long r) 48 { 49     if(l==r)return; 50     long long mid=(l+r)/2; 51     nxd2(l,mid);nxd2(mid+1,r); 52     long long z=l,y=mid+1,x=l; 53     while(z<=mid&&y<=r) 54     { 55         if(c[z]>=c[y]) 56         { 57             ans2+=mid-z+1; 58             d[x++]=c[y];y++; 59         } 60         else 61         { 62             d[x++]=c[z];z++; 63         } 64     } 65     while(z<=mid) 66     { 67         d[x++]=c[z];z++; 68     } 69     while(y<=r) 70     { 71         d[x++]=c[y];y++; 72     } 73     memcpy(c+l,d+l,(r-l+1)*8); 74 } 75 int main() 76 { 77     freopen("jian.in","r",stdin); 78     freopen("jian.out","w",stdout); 79     readlong(n);readlong(l);readlong(r); 80     for(long long i=1;i<=n;i++) 81     { 82         readlong(a[i]); 83         b[i]=b[i-1]+a[i]-l; 84         c[i]=c[i-1]+a[i]-r; 85     } 86     ans1=0;nxd1(0,n); 87     ans2=0;nxd2(0,n); 88     ans2-=ans1; 89     ans1=n*(n+1)/2; 90     if(ans2==0) 91     { 92         cout<<"0"<