题面

样例输入

第1行，包含三个整数。$n$，$L$，$R$。
第2行n个数，代表$a[1..n]$。

样例输出

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

思路

这题恶心啊，不过很显然可以知道这题是二分。可以直接二分最后的答案，但是$check$的复杂度貌似直接爆炸，看看这个$[L,R]$貌似可以优化的样子。考虑建立两个单调序列，对于每一个二分出的答案，在原权值上减去这个数值再做一个前缀和。那么我们的判断方法就是只要环上有任意一个长度在$[L,R]$区间中的子串的$sum[r]-sum[l]>=0$，$check$就可以$return 1$。因为长度必须为偶数，所以开始先判断一下，如果$l,r$为奇数那么就变成偶数。然后对于$L$到$2*n$(断环为链)的所有点$for$一遍每次加入$i-L$这个点的$sum$，维护一个单调上升的单调队列。然后从队头$pop$掉距离超过$R$的点。因为长度有奇偶性，所以搞两个队列维护（对于$i$为偶数长度的点对于$i+1$是奇数，但对于$i+2$又是偶数）需要注意的是记得保存最后选取的那段，然后处理输出答案。（记得开$long double$）

代码

#include<bits/stdc++.h>
#define LL long long
#define eps 1e-6
#define LB long double
#define Maxn 100005
using namespace std;
LL n,a[Maxn<<1],l,r,a1,a2,summ[Maxn<<1];
LB sum[Maxn<<1],ans;
inline void read(LL &x)
{
    LL f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
inline LL gcd(LL a,LL b)
{
	if (b==0) return a;return gcd(b,a%b);
}
inline bool check(LB x)
{
    deque<int> q[2];
    for (int i=1;i<=n<<1;i++) sum[i]=sum[i-1]+a[i]-x;
    for(int i=l;i<=n<<1;i++)
    {
        while(!q[i&1].empty()&&sum[i-l]<sum[q[i&1].back()]) q[i&1].pop_back();
        while(!q[i&1].empty()&&i-q[i&1].front()>r) q[i&1].pop_front();
        q[i&1].push_back(i-l);
        if(!q[i&1].empty()&&sum[i]-sum[q[i&1].front()]>=0) {a1=summ[i]-summ[q[i&1].front()],a2=i-q[i&1].front();return 1;}
	}
    return 0;
}
int main()
{
    read(n),read(l),read(r);
    for (int i=1;i<=n;i++) read(a[i]);
    for (int i=n+1;i<=n<<1;i++) a[i]=a[i-n];
    for (int i=1;i<=n<<1;i++) summ[i]=summ[i-1]+a[i];
  
    if (l&1) l++;if (r&1) r--; 
    LB L=0,R=1000000000;
    while (L+eps<R)
    {
        LB mid=(LB)(L+R)/2;
        if (check(mid)) ans=mid,L=mid;
        else R=mid;
    }  
    LL GCD=gcd(a1,a2);
    if (GCD==a2) cout<<a1/GCD<<endl; 
    else cout<<a1/GCD<<"/"<<a2/GCD<<endl;
    return 0;
}