题目描述

题目本质上就是求任意一个长度大于1的区间内的最大值和最小值的差值的总和。 如果暴力：就是两层循环10^5肯定要超时

思路

使用单调栈。

主要思想：反向思考

一个区间内的最大最小值必定是在给定的序列中------反向推导----> 求出序列中每个数所能包拢的最大或最小值范围，某个区间只要在该范围以内，并且取到该点的话，其最大或者最小值就是该点。 那么以该点为最大或者最小值的区间数目就有两种情况：（以最大值为例，l[i]为区间左端点，r[i]是右端点）

1. 以该点为端点，那么另一个端点就是从l[i]~r[i]中取且不包含i，就有r[i]-l[i]个
2. 如果该点不是端点，那么左端点由i-l[i]种取值，右端点由r[i]-i种取值，即有 (i-l[i])*(r[i]-i)个

正确性证明

为何这样子就能够取到所有区间的取值呢？ 利用反证法： 假设某个区间有某个最大/最小值x,并且区间不完全在如上所求的l[i]-r[i]里面，那么这就意味着：该区间的不属于l[i]-r[i]的部分的最大/最小值是x，由于l[i]~r[i]是x能成为最大/最小值的最大范围，所以这就矛盾了，故上述成立。

求l[i]和r[i]

利用单调栈来求，但是要考虑两个相同的数的处理，就是两个相等的数在某一个范围里面只能有一个取到该范围，不然会重复，所以就要选择其中一个优先（接下来的代码是按照右边优先） l和r一个从前往后循环、一个从后往前循环 求最大的范围和最小的范围只要把序列都取相反数就能得到相反的结果

//区间的价值为该区间内的最大差值
//暴力超时

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5 + 10;
stack<PII> stk;  // 一个是存数，一个存位置
int n;
int a[N];
LL l[N], r[N];
LL slove()
{
	while (stk.size()) stk.pop();
	
	
	for (int i = 1; i <= n; i++)
	{
		while (stk.size() && stk.top().x <= a[i]) stk.pop();  // 这里取等于是让右边的优先
		if (stk.size()) l[i] = stk.top().second + 1;
		else l[i] = 1;
		stk.push({ a[i],i });
	}
	while (stk.size()) stk.pop();
	for (int i = n; i >= 1; i--)
	{
		while (stk.size() && stk.top().x < a[i]) stk.pop();   // 由于这边是右边的优先，所以这里不能取等于
		if (stk.size()) r[i] = stk.top().second - 1;
		else r[i] = n;
		stk.push({ a[i],i });
	}

	LL ans = 0;
	for (int i = 1; i <= n; i++)
	{
		ans += (r[i] - l[i]) * a[i];
		ans += (i - l[i]) * (r[i] - i) * a[i];
	}
	return ans;
}


int main()
{
	
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		LL ans = slove();
		for (int i = 1; i <= n; i++)  a[i] = -a[i];  //取相反数
		ans += slove();
		cout << ans << endl;
	}
	
	
}