C++(g++ 7.5.0) 解法, 执行用时: 231ms, 内存消耗: 1072K, 提交时间: 2022-08-19 20:57:28

#include<cstdio>
int a[100003],s[100003];
void center()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	long ans=0;int _s=0;
	a[0]=0x7fffffff;s[0]=0;a[n+1]=0x7fffffff;
	for(int i=1;i<=n+1;i++)
	{
		while(a[i]>a[s[_s]])
			ans+=1l*(i-s[_s])*(s[_s]-s[_s-1])*a[s[_s]],_s--;
		s[++_s]=i;
	}
	_s=0;a[0]=s[0]=0;a[n+1]=0;
	for(int i=1;i<=n+1;i++)
	{
		while(a[i]<a[s[_s]])
			ans-=1l*(i-s[_s])*(s[_s]-s[_s-1])*a[s[_s]],_s--;
		s[++_s]=i;
	}
	printf("%ld\n",ans);
}
int main()
{
	int t;scanf("%d",&t);
	while(t--)center();
}

C++14(g++5.4) 解法, 执行用时: 215ms, 内存消耗: 12744K, 提交时间: 2020-07-15 12:33:43

#include<cstdio>
 
typedef long long ll;
const int maxn=1e5+50;
int T,n;
ll ans;
ll a[maxn],q[maxn];
 
ll c(){
  ll t=0,r=0,sum=0;
  for(int i=1;i<=n;i++){
    while(t>=1&&a[i]>a[q[t]]){sum-=a[q[t]]*(q[t]-q[t-1]);t--;}
    q[++t]=i;sum+=a[i]*(q[t]-q[t-1]);r+=sum;
  }
  return r;
}
 
int main(){
  scanf("%d",&T);
  while(T--){
    scanf("%d",&n);q[0]=0;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    ans=c();
    for(int i=1;i<=n;i++)a[i]=-a[i];
    ans+=c();
    printf("%lld\n",ans);
  }
  return 0;
}