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; 
}

谢谢