题解 | #情景剧#|并查集写法

参考 https://www.luogu.com.cn/blog/ak-ioi/solution-at2060 ，这题也可以这么维护。

我们可以枚举最小值，考虑找到一个最大区间使得其依然为最小值，由于区间最大，包含的点最多，人数最大化，最大值也尽可能地最大化了。

按照值不断从大到小激活点，对于一个点，激活时所在的连通块就表示其所能拓展的最大区间，然后再并查集上维护最大值和块大小即可。

代码有点累赘。

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const LL N=2*1e6+5;
struct node
{
	LL pos,num;
}b[N];
__int128 ans,mx[N];
LL n,a[N],fa[N],sz[N],vis[N];
bool cmp(node x,node y)
{
	return x.num>y.num;
}
LL find(LL x)
{
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);	
}
void add(LL x)
{
	vis[x]=1;
	if(vis[x-1])
	{
		LL fx=find(x),fy=find(x-1);
		if(mx[fx]<mx[fy])mx[fx]=mx[fy];
		fa[fy]=fx,sz[fx]+=sz[fy];
	}
	if(vis[x+1])
	{
		LL fx=find(x),fy=find(x+1);
		if(mx[fx]<mx[fy])mx[fx]=mx[fy];
		fa[fy]=fx,sz[fx]+=sz[fy];
	}
}
void print(__int128 x)
{
	if(x==0)return;
	print(x/10);
	putchar(x%10+'0');
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		fa[i]=i,sz[i]=1,mx[i]=a[i],b[i].num=a[i],b[i].pos=i;
	}
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		LL t=i;
		add(b[i].pos);
		while(b[t+1].num==b[i].num)t++,add(b[t].pos);
		for(int j=i;j<=t;j++)
		{
			LL p=find(b[j].pos);
			__int128 k=b[j].num*sz[p];
			k*=mx[p];
			ans=max(ans,k);
		}
		i=t;
	}
	if(ans==0)puts("0");
	else print(ans);
}