[TIOJ] 1637 我愛台灣

LINK：http://tioj.infor.org/problems/1637
　　不得不說，這題對於資料結構來說是非常精湛的一題。
　　我一開始用的是類似merge sort的方法，爆搜最大值TLE後寫了人生第一個的sparse table，MLE後換寫人生第一棵指標型線段樹，MLE之後就放棄而去看別人的code了，結果發現可以O(n)用stack維護出來QQ，我的資料結構還是學術不精啊@@
　　由於兩個基地台間的電波是以最大值決定，所以可以想到去維護一個遞減的stack(但我一開始沒去想QQ)，然後可以想像，假設在最右邊再蓋一個基地，就看看這個由於這個基地台而產生的新的電波值可以往左延伸多遠(也就是一直延伸到有電波值比它大的基地台之前)，然後就可以維護了XD，不過我是亂寫一個之後再亂debug後就AC了~~

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
vector<pair<int,int> > t;
int dianboi, ans;
main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 0; i < n-1; i++)
    {
        int a; cin >> a;
        while(!t.empty() && t.back().first < a)
        {
            pair<int,int> p = t.back(); t.pop_back();
            if(!t.empty())dianboi -= (p.second-t.back().second)*p.first;
            else dianboi -= (p.second+1)*p.first;
        }
        if(!t.empty()) dianboi += (i-t.back().second)*a;
        else dianboi += (i+1)*a;
        ans += dianboi;
        t.push_back({a,i});
    }
    cout << ans << '\n';
}