51nod-1215 數組的寬度(單調棧)

原題連結

1215 數組的寬度

題目來源：  Javaman 基準時間限制：1 秒 空間限制：131072 KB 分值: 80  難度：5級算法題

 收藏

 關注 N個整數組成的數組，定義子數組a[i]..a[j]的寬度為：max(a[i]..a[j]) - min(a[i]..a[j])，求所有子數組的寬度和。 Input

第1行：1個數N，表示數組的長度。(1 <= N <= 50000)
第2 - N + 1行：每行1個數，表示數組中的元素(1 <= A[i] <= 50000)      

Output

輸出所有子數組的寬度和。      

Input示例

5
1
2
3
4
5      

Output示例

20      

利用單調棧求出所有區間最大值之和，減去所有區間最小值之和

#include <bits/stdc++.h>
#define maxn 50005
#define MOD 1000000007
using namespace std;
typedef long long ll;

int s1[maxn], s2[maxn], k1, k2, num[maxn];
ll p1[maxn], p2[maxn];
int main(){
//	freopen("in.txt", "r", stdin);
	int n;
	k1 = 1, k2 = 1;
	ll ans1 = 0, ans2 = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	 scanf("%d", num+i);
	p1[0] = p2[0] = num[0];
	for(int i = 1; i < n; i++){
		while(k1){
			if(num[s1[k1-1]] <= num[i]){
				k1--;
			}
			else
			 break;
		}
		s1[k1] = i;
		if(k1 == 0){
			p1[k1] = (ll)(i + 1) * num[i];
		}
		else{
			p1[k1] = p1[k1-1] + (ll)(i - s1[k1-1]) * num[i];
		}
		ans1 += p1[k1];
		k1++;
		
		while(k2){
			if(num[s2[k2-1]] >= num[i]){
				k2--;
			}
			else
			 break;
		}
		s2[k2] = i;
		if(k2 == 0){
			p2[k2] = (ll)(i + 1) * num[i];
		}
		else{
			p2[k2] = p2[k2-1] + (ll)(i - s2[k2-1]) * num[i];
		}
		ans2 += p2[k2];
		k2++;
	}
	printf("%I64d\n", ans1 - ans2);
	return 0;
}