ZJ a813: 4. 城市觀測

題目鏈接:https://zerojudge.tw/ShowProblem?problemid=a813

連續寫了兩題有關單調性的題目,真的是有夠難寫的
這題其實是麻煩在有同樣高度的樓
我一直沒想到每新增一個等高樓就要再把答案加一次等高樓的數量
真的是白癡= =
這題的單調性就是如果有一個更高的樓出現
之前比他小的樓都不可能被看到
而如果是一個更矮的樓出現,則之前那些更高的樓會看不到他
再處理等高樓之後問題就解決了

以下為code

#include<bits/stdc++.h>

#include<bits/extc++.h>

using namespace std;

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

int main()

{

AC

int n,t;

ll r=0;

cin>>n>>t;

deque<int> dq;

unordered_map<int,int> m;

dq.emplace_back(t);

m[t]++;

for(int i=1;i<n;i++)

{

cin>>t;

while(dq.size()&&t>dq.back())

{

r+=m[dq.back()];

m[dq.back()]=0;

dq.pop_back();

}

if(dq.size()&&t==dq.back()) r+=m[t];

else dq.emplace_back(t);

m[t]++;

if(dq.size()>1) r++;

}

cout<<r*2<<'\n';

}