bzoj3316: JC loves Mkk

时间:2022-06-16 16:31:57

Description

bzoj3316: JC loves Mkk

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 ;
}