Description
Input
第1行，包含三个整数。n，L，R。
第2行n个数，代表a[1..n]。
Output
仅1行，表示询问答案。
如果答案是整数，就输出整数；否则，输出既约分数“P/Q”来表示。
随机数据不卡精度所以可以分数规划二分答案
用两个单调队列维护奇偶位置上的前缀和，可以判定是否存在在[L,R]内的正权值偶数长度子串
#include<cstdio>
typedef long long i64;
char buf[],*ptr=buf-;
int _(){
int x=,c=*++ptr;
while(c<)c=*++ptr;
while(c>)x=x*+c-,c=*++ptr;
return x;
}
int n,l,r;
int a[];
double s[];
int s1[],s2[],l1,r1,l2,r2;
i64 gcd(i64 a,i64 b){
for(i64 c;b;c=a,a=b,b=c%b);
return a;
}
int main(){
buf[fread(buf,,sizeof(buf),stdin)]=;
n=_();l=_();r=_();
if(l&)++l;
if(r&)--r;
double L=,R=;
for(int i=;i<=n;++i){
a[i]=_();
if(a[i]>R)R=a[i];
a[n+i]=a[i];
}
int lp=,rp=;
while(L<R){
double M=(L+R)/;
int l0=,r0=;
l1=l2=;r1=r2=;
for(int i=;i<=n*;++i){
s[i]=s[i-]+a[i]-M;
if(i-l>=){
if(i-l&){
while(l1<=r1&&s[s1[r1]]>s[i-l])--r1;
s1[++r1]=i-l;
}else{
while(l2<=r2&&s[s2[r2]]>s[i-l])--r2;
s2[++r2]=i-l;
}
}
if(i&){
while(l1<=r1&&s1[l1]<i-r)++l1;
if(l1<=r1&&s[s1[l1]]<s[i]){
l0=s1[l1]+;
r0=i;
break;
}
}else{
while(l2<=r2&&s2[l2]<i-r)++l2;
if(l2<=r2&&s[s2[l2]]<s[i]){
l0=s2[l2]+;
r0=i;
break;
}
}
}
if(l0){
lp=l0;rp=r0;
L=M+1e-;
}else R=M-1e-;
}
i64 A=,B=rp-lp+,g;
for(int i=lp;i<=rp;++i)A+=a[i];
g=gcd(A,B);
A/=g;B/=g;
if(B==)printf("%lld",A);
else printf("%lld/%lld",A,B);
return ;
}