[TIOJ] 1721. 山上的風景

題目連結:http://tioj.infor.org/problems/1721

---

往右往左各分別維護一個遞減的stack，而若是塞入的東西比較大，則就把比他小的全部pop掉，同時也保證他們都只能看到這裡。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second
const int N = 100000 + 5;

int arr[N], ans[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n){
		for(int i=0;i<n;i++) cin>>arr[i];
		stack<PII> ss;
		for(int i=0;i<n;i++){
			while(!ss.empty() and ss.top().FF <= arr[i]){
				ans[ss.top().SS] = i-ss.top().SS+1;
				ss.pop();
			}
			ss.push({arr[i], i});
		}
		while(!ss.empty()){
			ans[ss.top().SS] = n-ss.top().SS;
			ss.pop();
		}
		for(int i=n-1;i>=0;i--){
			while(!ss.empty() and ss.top().FF <= arr[i]){
				ans[ss.top().SS] += ss.top().SS-i;
				ss.pop();
			}
			ss.push({arr[i], i});
		}
		while(!ss.empty()){
			ans[ss.top().SS] += ss.top().SS;
			ss.pop();
		}
		for(int i=0;i<n;i++) cout<<ans[i]<<" \n"[i==n-1];
	}
	return 0;
}