CF817D Imbalanced Array
解题思路
根据一位巨佬的题解
枚举当前点在什么区间内是最小值和最大值
可以用四个单调栈
一个找当前点为区间最小值时,区间的最左端(minl)
一个找当前点为区间最小值时,区间的最右端(minr)
一个找当前点为区间最大值时,区间的最左端(maxl)
一个找当前点为区间最大值时,区间的最右端(maxr)
最后用一个乘法
a[i]*1ll*(1ll*(i-maxl[i])*(maxr[i]-i)-1ll*(i-minl[i])*(minr[i]-i));
再累加就AC了
注意:要特判
AC代码
#include<cstdio>
#include<iostream>
using namespace std;
long long n,s,tail,a[1000005],f[1000005],minl[1000005],minr[1000005],maxl[1000005],maxr[1000005];
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
f[1]=0;//初值
tail=1;
for(int i=1;i<=n;i++)//找最小值时区间最左端
if(a[i]>a[f[tail]])//特判
{
minl[i]=i-1;//值不一样
f[++tail]=i;//进栈
}
else
{
while(a[i]<a[f[tail]]&&tail>=1)tail--;//出栈
minl[i]=f[tail];
f[++tail]=i;//进栈
}
f[1]=n+1; //初值
tail=1;
for(int i=n;i>=1;i--)//找最小值时区间最右端
if(a[i]>a[f[tail]])//特判
{
minr[i]=i+1;//值不一样
f[++tail]=i;//进栈
}
else
{
while(a[i]<=a[f[tail]]&&tail>=1)tail--;//出栈
minr[i]=f[tail];
f[++tail]=i;//进栈
}
a[0]=a[n+1]=2147483647;//初值
f[1]=0;
tail=1;
for(int i=1;i<=n;i++)找最大值时区间最左端
if(a[i]<a[f[tail]])//特判
{
maxl[i]=i-1;//值不一样
f[++tail]=i;//进栈
}
else
{
while(a[i]>a[f[tail]]&&tail>=1)tail--;//出栈
maxl[i]=f[tail];
f[++tail]=i;//进栈
}
f[1]=n+1;//初值
tail=1;
for(int i=n;i>=1;i--)找最大值时区间最右端
if(a[i]<a[f[tail]])//特判
{
maxr[i]=i+1;//值不一样
f[++tail]=i;//进栈
}
else
{
while(a[i]>=a[f[tail]]&&tail>=1)tail--;//出栈
maxr[i]=f[tail];
f[++tail]=i;//进栈
}
for(int i=1;i<=n;i++)//1 to n
s+=a[i]*1ll*(1ll*(i-maxl[i])*(maxr[i]-i)-1ll*(i-minl[i])*(minr[i]-i));//乘法和加法
cout<<s;
}