阿卡分糖果（滑动窗口）

阿卡分糖果

时间限制: 10 Sec 内存限制: 128 MB

题目描述

阿卡的冬眠营马上要结束啦，他正在为这次活动筹办一场闭幕式。闭幕式上他策划了许多精彩的小游戏，并且打算用糖果作为这些小游戏的奖品。但是分糖果成为了一个难题。
阿卡一共让大家玩了M轮小游戏，每一轮都有一个胜出者，阿卡要给他们其中的每个人分一些糖果。
给每个人分相同数量的糖果虽然公平，但这太不符合阿卡的作风了，于是阿卡写了一个随机的小程序，为每个人随机出了一个糖果数量，准备下发。
阿瓦这时走到了阿卡的后面，看到他列出的分糖果的方案，吃了一惊，提醒阿瓦这样分糖果可能有人会报警。
原来阿瓦给了1号胜利者105个糖果，却只给了2号胜利者1个糖果。
为了科学而有趣地制定分糖果的方案，阿卡设计了一个胜利者们不开心程度的函数。这个函数是这样计算的：
假设第i位胜利者获得了Ai颗糖果。对于每个连续的区间[l,r](1≤l≤r≤n)，设其中Ai的最大值为Max，Ai的最小值为Min，那么就将Max−Min累积到答案当中。
请你帮阿卡计算一下胜利者们不开心的程度，即

输入

第一行，一个整数n，表示胜利者的人数。
第二行，n个整数，第i个数Ai，表示第i位胜利者分到的糖果数。

输出

共一行，一个整数，表示胜利者们不开心的程度。

样例输入

复制样例数据

3
3 3 2

样例输出

提示

对于50%的数据，n≤3000。
对于100%的数据，n≤105 0<Ai≤106。

很经典的滑动窗口求任意区间最大最小值的差（r>=l）

第一次遍历用单调队列维护最大值，第二遍用单调队列维护最小值。。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n;
int a[100005], lows[100005], highs[100005];
LL ans;

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
	}
	int top = 0;
	LL ans = 0, sum = 0;
	for (int i = 1; i <= n; i++){
		while(top > 0 && a[highs[top]] < a[i]){
			sum -= a[highs[top]] * (highs[top] - highs[top - 1]);
			top--;
		}
		highs[++top] = i;
		sum += a[i] * (highs[top] - highs[top - 1]);
		ans += sum;
	}
	sum = 0, top = 0;
	for (int i = 1; i <= n; i++){
		while(top > 0 && a[lows[top]] > a[i]){
			sum -= a[lows[top]] * (lows[top] - lows[top - 1]);
			top--;
		}
		lows[++top] = i;
		sum += a[i] * (lows[top] - lows[top - 1]);
		ans -= sum;
	}
	printf("%lld\n", ans);

	return 0;
}
/**/