[TIOJ] 1637. 我愛台灣

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

---

枚舉每個點，看有哪些區間會以他為最大值，若是裸著做可能會有個$O(n^2)$的作法，但是其實會發現維護那些區間會以他為最大值，其實可以先找出最長且以他為最大值的區間，而要做這件事就只要用個stack維護一下左邊右邊第一個比自己大的數在哪就好(維護stack的遞減性就可做到)。維護好後算答案其實也不難，區間的可能個數就是右邊元素的數量乘以左邊元素的數量。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<lld, int> PLI;
#define FF first
#define SS second
const int N = 1000000 + 5;

lld arr[N], LL[N], RR[N];
vector<PLI> ss;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n-1;i++) cin>>arr[i];
	for(int i=0;i<n-1;i++){
		while(!ss.empty() and ss.back() < (PLI){arr[i], i}) ss.pop_back();
		LL[i] = ss.empty()?-1:ss.back().SS;
		ss.push_back({arr[i], i});
	}
	ss.clear();
	for(int i=n-2;i>=0;i--){
		while(!ss.empty() and ss.back() < (PLI){arr[i], i}) ss.pop_back();
		RR[i] = ss.empty()?n-1:ss.back().SS;
		ss.push_back({arr[i], i});
	}
	lld ans = 0;
	for(int i=0;i<n-1;i++) ans += arr[i]*(RR[i]-i)*(i-LL[i]);
	cout<<ans<<'\n';
	return 0;
}