XTU 1205 Range 2014湖南邀请赛C 单调栈

ACM

题目地址：XTU 1205

题意： 
在一个序列A中，Range(A)=Max(A)-Min(A)+1; 
求一个序列的子序列中所有子序列的Range的和。

分析： 
做了好久。。。多谢Tamara巨巨的指点。 
1 2 3 4 5 
Range(A)=Max(A)-Min(A)+1; 
先别看后面的+1 
统计每一位会增加的次数以及会减少的次数。

1. 先看会增加的,x表示左边小的个数，y表示右边小或等于的个数 
   当i=1, x = 0, y = 0, det = 0 
   当i=2, x = 1, y = 0, det = (1+0+0)*2 
   当i=3, x = 2, y = 0, det = (2+0+0)*3 
   当i=4, x = 3, y = 0, det = 3*4 
   当i=5, x = 4, y = 0, det = 4*5

2. 再看会减少的,x表示左边大的个数，y表示右边大或等于的个数 
   当i=1, x = 0, y = 4, det = 4*1 
   当i=2, x = 0, y = 3, det = 3*2 
   当i=3, x = 0, y = 2, det = 2*3 
   当i=4, x = 0, y = 1, det = 1*4 
   当i=5, x = 0, y = 0, det = 0*5

所以，ans=2+6+12+20-4-6-6-4=20 
由于还要+1，所以还要加n*(n+1)/2。

我们只要用单调栈求出需要的x和y就行了。

代码：

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  File:        C.cpp
*  Create Date: 2014-06-07 15:41:15
*  Descripton:   
*/

#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;

const int N = 1e5 + 10;

stack<int> s, ss;

int t, n;
int a[N], big[N], bige[N];
ll ans, tmp;

int main()
{
	scanf("%d", &t);
	for (int cas = 1; cas <= t; cas++) {
		scanf("%d", &n);
		while (!s.empty())
			s.pop();
		while (!ss.empty())
			ss.pop();
		for (int i = 0; i < n; i++) {
			scanf("%d", &a[i]);
			// 左边小的个数
			while (!s.empty() && a[s.top()] > a[i])
				s.pop();
			if (s.empty())
				big[i] = i;
			else
				big[i] = i - s.top() - 1;
			s.push(i);
			// 左边大的个数
			while (!ss.empty() && a[ss.top()] < a[i])
				ss.pop();
			if (ss.empty())
				bige[i] = i;
			else
				bige[i] = i - ss.top() - 1;
			ss.push(i);
		}
		while (!s.empty())
			s.pop();
		while (!ss.empty())
			ss.pop();
		ans = 0;
		for (int i = n - 1; i >= 0; i--) {
			// 右边小或等于的个数
			while (!s.empty() && a[s.top()] >= a[i])
				s.pop();
			if (s.empty())
				tmp = n - i - 1;
			else
				tmp = s.top() - i - 1;
			ans -= (tmp + big[i] + tmp * big[i]) * a[i];
			s.push(i);
			// 右边大或等于的个数
			while (!ss.empty() && a[ss.top()] <= a[i])
				ss.pop();
			if (ss.empty())
				tmp = n - i - 1;
			else
				tmp = ss.top() - i - 1;
			ans += (tmp + bige[i] + tmp * bige[i]) * a[i];
			ss.push(i);
		}
		ans += n * (n + 1) / 2;
		printf("Case %d: ", cas);
		cout << ans << endl;
	}
	return 0;
}