题解 | #情景剧#|并查集写法
情景剧
https://ac.nowcoder.com/acm/contest/65192/A
参考 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);
}