首页 > 代码库 > bzoj3316: JC loves Mkk

bzoj3316: JC loves Mkk

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[10000007],*ptr=buf-1;int _(){    int x=0,c=*++ptr;    while(c<48)c=*++ptr;    while(c>47)x=x*10+c-48,c=*++ptr;    return x;}int n,l,r;int a[200007];double s[200007];int s1[200007],s2[200007],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,1,sizeof(buf),stdin)]=0;    n=_();l=_();r=_();    if(l&1)++l;    if(r&1)--r;    double L=0,R=0;    for(int i=1;i<=n;++i){        a[i]=_();        if(a[i]>R)R=a[i];        a[n+i]=a[i];    }    int lp=0,rp=0;    while(L<R){        double M=(L+R)/2;        int l0=0,r0=0;        l1=l2=1;r1=r2=0;        for(int i=1;i<=n*2;++i){            s[i]=s[i-1]+a[i]-M;            if(i-l>=0){                if(i-l&1){                    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&1){                while(l1<=r1&&s1[l1]<i-r)++l1;                if(l1<=r1&&s[s1[l1]]<s[i]){                    l0=s1[l1]+1;                    r0=i;                    break;                }            }else{                while(l2<=r2&&s2[l2]<i-r)++l2;                if(l2<=r2&&s[s2[l2]]<s[i]){                    l0=s2[l2]+1;                    r0=i;                    break;                }            }        }        if(l0){            lp=l0;rp=r0;            L=M+1e-8;        }else R=M-1e-8;    }    i64 A=0,B=rp-lp+1,g;    for(int i=lp;i<=rp;++i)A+=a[i];    g=gcd(A,B);    A/=g;B/=g;    if(B==1)printf("%lld",A);    else printf("%lld/%lld",A,B);    return 0;}

 

bzoj3316: JC loves Mkk