记录编号	337975	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	__卡片游戏	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	2.596 s
提交时间	2016-11-05 06:10:39	内存使用	9.83 MiB

#include <cstdio>
#include <algorithm>
typedef long long TYPE;
const int MAXN=500010;
TYPE gcd(TYPE a,TYPE b){
	return b==0?a:gcd(b,a%b);
}
struct FFT{
	int c[MAXN],N;
	void change(int pos,int val){
		while(pos<=N){
			c[pos]+=val;
			pos+=pos&-pos;
		}
	}
	int ask(int pos){
		int ans=0;
		while(pos){
			ans+=c[pos];
			pos-=pos&-pos;
		}return ans;
	}
}st,sc;
int w[MAXN],f[MAXN],p[MAXN];
int main(){
	freopen("xgame.in","r",stdin);freopen("xgame.out","w",stdout);
	int N,L,R;TYPE ans=0;
	scanf("%d%d%d",&N,&L,&R);
	++N;st.N=N;
	for(int i=2;i<=N;++i)
	{
		scanf("%d",&w[i]);
	}f[1]=p[1]=0;
	for(int i=2;i<=N;++i)
	{
		f[i]=f[i-1]+w[i]-L;
		p[i]=f[i];
	}
	std::sort(p+1,p+N+1);
	for(int i=1;i<=N;++i)
	{
		f[i]=std::lower_bound(p+1,p+N+1,f[i])-p;
		ans+=st.ask(f[i]);
		st.change(f[i],1);
	}
	st=sc;st.N=N;p[1]=f[1]=0;
	for(int i=2;i<=N;++i){
		f[i]=f[i-1]+w[i]-R;
		p[i]=f[i];
	}//printf("%lld\n",ans);
	std::sort(p+1,p+N+1);
	for(int i=1;i<=N;++i){
		f[i]=std::lower_bound(p+1,p+N+1,f[i])-p;
		ans-=st.ask(f[i]-1);
		st.change(f[i],1);
	}--N;
	TYPE c=(1ll*N*(N+1))>>1;//printf("%lld %lld\n",ans,c);
	if(ans==0)printf("0");
	else if(ans==c)printf("1");
	else {TYPE a=gcd(c,ans);printf("%lld/%lld",ans/a,c/a);}
	while(getchar()!=EOF);
	return 0;
}