Description

Input

第1行，包含三个整数。n，L，R。

第2行n个数，代表a[1..n]。

Output

仅1行，表示询问答案。

如果答案是整数，就输出整数；否则，输出既约分数“P/Q”来表示。

 

Sample Input

5 3 4

3 1 2 4 5

Sample Output

7/2

HINT

1≤L≤R≤n≤10^5，0≤ai≤10^9，保证问题有解,数据随机生成

 

 

首先这是一个分数规划，于是我们得二分，设答案为mid，那么原数列变成a[i]-mid，然后就是要找一段使得区间和大于0

前缀和可以先预处理，然后找到满足s[j]<s[i]且i<j的j，发现满足条件的j中s[j]越小越好，于是用单调队列维护

然后得保证选的数的个数是偶数，于是开两个单调队列，分别维护位置为奇数和偶数的

1 //minamoto 2 #include
      
        3 #include
       
         4 #define ll long long 5 using namespace std; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1=buf,*p2=buf; 8 template
        
         inline bool cmax(T&a,const T&b){
    return a
         
          inline bool cmin(T&a,const T&b){
    return a>b?a=b,1:0;}10 int read(){11     #define num ch-'0'12     char ch;bool flag=0;int res;13     while(!isdigit(ch=getc()))14     (ch=='-')&&(flag=true);15     for(res=num;isdigit(ch=getc());res=res*10+num);16     (flag)&&(res=-res);17     #undef num18     return res;19 }20 const int N=1e5+5;21 int n,m,L,R,h1,h2,t1,t2;ll ans1,ans2,g,A[N<<1],S[N<<1];22 double v[N<<1],s[N<<1];int q1[N<<1],q2[N<<1];23 ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;}24 bool check(double x){25     for(int i=1;i<=m;++i) v[i]=A[i]-x,s[i]=s[i-1]+v[i];26     h1=h2=t1=1,t2=0,q1[1]=0;27     for(int i=L;i<=m;++i){28         while(h1<=t1&&q1[h1]
          
           =s[i-L+1]) --t1;38             q1[++t1]=i-L+1;39         }else{40             while(h2<=t2&&s[q2[t2]]>=s[i-L+1]) --t2;41             q2[++t2]=i-L+1;42         }43     }44     return 0;45 }46 int main(){47 //    freopen("testdata.in","r",stdin);48     n=read(),L=read(),R=read(),m=n<<1;49     double l=1<<30,r=0;50     for(int i=1;i<=n;++i) A[i]=A[i+n]=read(),cmin(l,(double)A[i]),cmax(r,(double)A[i]);51     for(int i=1;i<=m;i++) S[i]=S[i-1]+A[i];52     for(int i=1;i<=50;++i){53         double mid=(l+r)/2;54         check(mid)?l=mid:r=mid;55     }56     printf("%lld/%lld",ans1,ans2);57     return 0;58 }