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

题目大意

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

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

$1\le n\le 2\times 10^6,1\le h_i\le 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
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41