牛课网 Neat Tree（单调栈）

我会带着你远行 2022-05-26 10:40 126阅读 0赞

## [https://www.nowcoder.com/acm/contest/106/I][https_www.nowcoder.com_acm_contest_106_I]题目描述  ##

It’s universally acknowledged that there’re innumerable trees in the campus of HUST.

There is a row of trees along the East-9 Road which consists of N trees. Now that we know the height of each tree, the gardeners of HUST want to know the super-neatness of this row of trees. The neatness of a sequence of trees is defined as the difference between the maximum height and minimum height in this sequence. The super-neatness of this sequence of trees is defined as the sum of neatness of all continous subsequences of the trees.

Multiple cases please process until the end of input. There are at most 100 test cases.

## 输入描述: ##

For each case:
    The first line contains an integer N represents the number of

trees.

The next line n positive integers followed, in which h i ![304721_1524741510969_equation_tex_281_5Cleq_20h_7Bi_7D_20_5Cleq_2010_5E_7B6_7D_29][] represent the

height of the tree i.

## 输出描述: ##

For each test case, output a integer in a single line which represents the super-neatness of the row
    of trees.

示例1

## 输入 ##

3
    1 3 1
    4
    1 2 3 4

## 输出 ##

6
    10

## 说明 ##

As for the first case, the super-neatness of the row of trees [1, 3, 1] is 6, because there are 6 different subsequence of this row of trees: [1] (from index 0 to index 0), neatness is 0; [1, 3] (from index 0 to index 1), neatness is 2; [1, 3, 1] (from index 0 to index 2), neatness is 2; [3] (from index 1 to index 1), neatness is 0; [3, 1] (from index 1 to index 2), neatness is 2; [1] (from index 2 to index 2), neatness is 0.

思路：不错的一个单调栈，正常思路的话就是枚举每一个区间，然后最大值减去最小值求和，但这样会超时，我们可以用单调栈，先将每个区间的最大值加起来，再将每个区间最小值加起来，做差就是答案。

#include<cstdio>
    #include<queue>
    #include<stack>
    #include<iostream>
    using namespace std;
    const int maxn=1e6+10;
    typedef long long ll;
    int l[maxn], r[maxn];
    ll h[maxn];
    
    int main(){
    	int n;
    	while(~scanf("%d", &n))
    	{
    		for(int i=1; i<=n; i++)
    			scanf("%lld", &h[i]);
    		stack<int> s;
    		
    		for(int i=1; i<=n; i++)
    		{
    			while(!s.empty() && h[i]>=h[s.top()]) s.pop();//注意等号问题，因为区间不要重复。
    			if(s.empty())	l[i]=0;
    			else	l[i]=s.top();
    			
    			s.push(i);
    		}
    		
    		while(!s.empty()) s.pop();
    		
    		for(int i=n; i>=1; i--)
    		{
    			while(!s.empty() && h[i]>h[s.top()]) s.pop();
    			if(s.empty())  r[i]=n+1;
    			else 	r[i]=s.top();
    			
    			s.push(i);
    		}
    		ll ans=0;
    		for(int i=1; i<=n; i++)
    			ans+=h[i]*(i-l[i])*(r[i]-i);
    		
    		while(!s.empty()) s.pop();
    		for(int i=1; i<=n; i++)
    		{
    			while(!s.empty() && h[i]<=h[s.top()]) s.pop();
    			if(s.empty()) l[i]=0;
    			else l[i]=s.top();
    			s.push(i);
    		}
    		
    		while(!s.empty()) s.pop();
    		for(int i=n; i>=1; i--){
    			while(!s.empty() && h[i]<h[s.top()]) s.pop();
    			
    			if(s.empty()) r[i]=n+1;
    			else r[i]=s.top();
    			s.push(i);
    		}
    		
    		for(int i=1; i<=n; i++)
    			ans-=h[i]*(i-l[i])*(r[i]-i);
    		
    		printf("%lld\n", ans);
    	}
    
    	return 0;
    }

[https_www.nowcoder.com_acm_contest_106_I]: https://www.nowcoder.com/acm/contest/106/I
[304721_1524741510969_equation_tex_281_5Cleq_20h_7Bi_7D_20_5Cleq_2010_5E_7B6_7D_29]: /images/20220526/c4d35539d6f34a038e7054c1f18ddc33.png