2023牛客OI赛前集训营-提高组（第一场）情景剧

本文主要是介绍2023牛客OI赛前集训营-提高组（第一场）情景剧，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

有一个长度为 $n$ 的序列 $h_i$ ，一段区间 $[l, r]$ 的有趣程度为这段区间上 $h_i$ 的最大值 $\times$ 最小值 $\times$ 区间长度。求所有区间中有趣程度的最大值，输出这个最大值。

保证答案在 $\text{unsigned long long}$ 的范围内。

$1\leq n\leq 2\times 10^6,1\leq h_i\leq 10^9$

题解

假设我们已经确定了区间的最小值 $h_i$ ，那么对于包含 $h_i$ 的区间 $[l, r]$ ，在保证区间中 $h_i$ 为最小值的情况下，则区间长度肯定是越大越好（因为取的数越多，最大值只会增大或不变，而区间长度只会增大，有趣程度也就不断增大了）。

也就是说，对于每个 $h_i$ ，求出以 $h_i$ 最小值的最大区间，并用这个区间来更新答案即可。

那怎么求以 $h_i$ 最小值的最大区间呢？用并查集可以解决。

我们可以按 $h_i$ 的值从大到小枚举 $h_i$ ，对于一个 $h_i$ ，如果 $h_{i-1}$ 在之前就被枚举过了，那么显然其值是比 $h_i$ 大的，其所在联通块的最小值也一定比 $h_i$ 大（在连通块中的都是在之前被枚举过的 $h$ 值），那么就将 $h_i$ 加入 $h_{i-1}$ 所在的连通块。对 $h_{i+1}$ 也是如此。然后， $h_i$ 所在的连通块即为以 $h_i$ 最小值的最大区间，用这个区间更新答案即可。

时间复杂度为 $O(n\cdot \alpha(n))$ 。

code

#include<bits/stdc++.h>
using namespace std;
int n,v[2000005],id[2000005],fa[2000005],siz[2000005],z[2000005];
unsigned long long mn[2000005],mx[2000005];
unsigned long long ans=0;
bool cmp(int ax,int bx){return v[ax]>v[bx];
}
int find(int ff){if(fa[ff]!=ff) fa[ff]=find(fa[ff]);return fa[ff];
}
void pt(int x,int y){x=find(x);y=find(y);if(x==y) return;fa[y]=x;siz[x]+=siz[y];mn[x]=min(mn[x],mn[y]);mx[x]=max(mx[x],mx[y]);ans=max(ans,mx[x]*mn[x]*siz[x]);
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&v[i]);ans=max(ans,1ull*v[i]*v[i]);mn[i]=mx[i]=v[i];siz[i]=1;fa[i]=id[i]=i;}sort(id+1,id+n+1,cmp);for(int i=1;i<=n;i++){int x=id[i];z[x]=1;if(z[x-1]) pt(x-1,x);if(z[x+1]) pt(x+1,x);}printf("%llu",ans);return 0;
}