让我们发扬人类智慧。

根据数学直觉，答案所在区间不会太长。

于是枚举长度为 $[l,\min(l+x,u)]$ 的区间便可以找到答案。

令 x=5000，可以 500 ms 内轻松通过。\

AC code

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second 
#define pb push_back
#define int long long
const int N = 2e5+10;
long long a[N];
long long sum[N];
void solve()
{
    return;
}
int u,v,n;
int p,q;
signed main()
{
    cin>>n>>u>>v;
    p=0;q=1;
    for(int i=1;i<=n;i++) cin>>a[i],a[i+n]=a[i];
    for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i];
    for(int i=((u+1)/2)*2;i<=min(u+5000,v);i+=2)
    {
        long long maxn=0;
        for(int j=1;j+i-1<=2*n;j++)
        {
            // cout<<j<<' '<<sum[j+i-1]<<' '<<sum[j-1]<<'\n';
            maxn=max(maxn,sum[j+i-1]-sum[j-1]);
        }
        if(maxn*q>p*i) p=maxn,q=i;
    }
    // cout<<p<<' '<<q<<'\n';
    int tmp=__gcd(p,q);
    p/=tmp;q/=tmp;
    cout<<p;
    if(q>1) cout<<'/'<<q;
    return 0;
}

看到环果断断链、倍增

看到平均值最大果断二分答案

看到长度限制 [L, U] 果断单调队列

对数组维护一个前缀和，对前缀和维护单调递增的单调队列

每扫过一个数sum[i]，将sum[i-L]加入单调队列，再把距离i超过R的点删掉

长度为偶数？对奇数位置和偶数位置分别维护一个单调队列即可

=======================================

二分答案 ans

之后将所有数全部减去ans，如果存在一个连续子序列满足

①和为正；②长度为偶数且在范围[L, U]内

说明答案比ans大，否则比ans小

可以求出前缀和并用单调队列维护，就可以O(n)判定了

提示：对于当前sum[i]，一定是尽可能找到最小的sum[j] (i-j∈[L, U] && ((i-j)%2==0) )

来判定sum[i]-sum[j]是否大于0

细节比较多：

①它是个环，所以要先把数组复制一遍并接在后面

②因为长度是偶数，所以要两次单调队列，一次处理0,2,4,6,8…，一次处理1,3,5,7,9,…

③因为长度不能小于L， 所以当你遍历到sum[i]时，肯定是将sum[i-L]或者sum[i-L-1]加入队列