题解：P12241 [蓝桥杯 2023 国 C] 最大区间

Fengwuy1 · 2025-05-13 22:16:29 · 题解

竟然没有人用悬线法。

思路：

我们可以假设以某一个 A_i 为最小值，使其向左右延伸。显然地，延伸的区间越长越好，那就可以用悬线法求出区间（即求出左右第一个大于它的位置。），最后求最大值即可。

悬线法：

定义 l_i 为当前找到的 i 位置的悬线能扩展到的最左边的位置，容易得到 l_i 初始为 i，我们需要进一步判断还能不能进一步往左扩展。

如果当前 l_i = 1，则已经扩展到了边界，不可以。

如果当前 a_i > a_{l_i - 1}，则从当前悬线扩展到的位置不能再往左扩展了。

如果当前 a_i \le a_{l_i - 1}，则从当前悬线还可以往左扩展，并且 l_i - 1 位置的悬线能向左扩展到的位置，i 位置的悬线一定也可以扩展到，于是我们将 l_i 更新为 l_{l_i - 1}，并继续执行判断（内容来自悬线法）。

代码：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=3e5+5;
int n,ans;
long long a[N],l[N],r[N];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        l[i]=r[i]=i;
    }   
    for(int i=1;i<=n;i++)
        while(l[i]>1&&a[i]<=a[l[i]-1])l[i]=l[l[i]-1];
    for(int i=n;i>=1;i--)
        while(r[i]<n&&a[i]<=a[r[i]+1])r[i]=r[r[i]+1];
    for(int i=1;i<=n;i++)
        if((r[i]-l[i]+1)*a[i]>ans)
            ans=(r[i]-l[i]+1)*a[i];
    cout<<ans;
    return 0;
}