HN Training 2015 Round9 Date（主席树+概率+组合数）

---

首先求出$[L,R]$中有多少个数比$F[i]$大，这个用主席树来处理就行。

然后问题就转化成了有$n$个数，其中有$k$个满足条件的数，然后随机取$x$个数，$x$随机产生，问选出的所有数都是满足条件的数的概率。

考虑枚举$x$，那么令$P[x]$表示选$x$个数都满足条件的概率,那么

$$
Ans=\frac{1}{n}\sum_{x=1}^{k}P[x]=\frac{1}{n}\sum_{x=1}^{k}\frac{C_{k}^{x}}{C_{n}^{x}}=\frac{1}{n}\sum_{x=1}^{k}\frac{k!(n-x)!}{n!(k-x)!}=\frac{k!}{n\cdot n!}\sum_{x=1}^{k}\frac{(n-x)!}{(k-x)!}
$$
然后只需要计算$\sum_{x=1}^{k}\frac{(n-x)!}{(k-x)!}$即可。

$$
Ans=\frac{k!}{n\cdot n!}\sum_{x=1}^{k}\frac{(n-x)!}{(k-x)!}=\frac{k!(n-k)!}{n\cdot n!}\sum_{x=1}^{k}\frac{(n-x)!}{(k-x)!(n-k)!}=\frac{\sum_{x=1}^{k}C_{n-x}^{k-x}}{n\cdot C_{n}^{k}}=\frac{\sum_{x=0}^{k}C_{n-x}^{k-x}}{n\cdot C_{n}^{k}}-\frac{1}{n}
$$
注意到$\sum_{x=0}^{k}C_{n-x}^{k-x}=C_{n+1}^{k}$，只需要将$C_{n-k}^{0}$换成$C_{n-k+1}^{0}$即得证。那么得到

$$
Ans=\frac{C_{n+1}^{k}-C_{n}^{k}}{n\cdot C_{n}^{k}}=\frac{C_{n}^{k-1}}{n\cdot C_{n}^{k}}=\frac{k}{n\cdot(n-k+1)}
$$
最后乘上$10^5$就行了。

---

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 100005
using namespace std;
const int T=1e5;
int n,m,A[N];
int tot,rt[N<<5],ls[N<<5],rs[N<<5],v[N<<5];
int CP(int p)
{
	int o=++tot;
	ls[o]=ls[p];
	rs[o]=rs[p];
	v[o]=v[p];
	return o;
}
int ADD(int p,int l,int r,int k)
{
	int o=CP(p);v[o]++;
	if(l==r)return o;
	int mid=l+r>>1;
	if(k<=mid)ls[o]=ADD(ls[o],l,mid,k);
	else rs[o]=ADD(rs[o],mid+1,r,k);
	return o;
}
int Gans(int lp,int rp,int l,int r,int k)
{
	if(k<=l)return v[rp]-v[lp];
	int mid=l+r>>1,sum=0;
	if(k<=mid)sum+=Gans(ls[lp],ls[rp],l,mid,k);
	sum+=Gans(rs[lp],rs[rp],mid+1,r,k);
	return sum;
}
int main()
{
	int i,j,k,x,y,t;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&A[i]);
	for(i=1;i<=n;i++)rt[i]=ADD(rt[i-1],1,T,A[i]);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&k);
		t=y-x+1;k=Gans(rt[x-1],rt[y],1,T,k);
		double ans=1e5*k/(1.0*t)/(1.0*t+1.0-1.0*k);
		printf("%.3lf\n",ans);
	}
}