[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] =...