单调栈
单调栈接触挺久了,一直没有仔细研究。
昨天模拟赛,一道单调栈没有看出来。
现在认真学学!
对于这道题,因为它是连续子序列
所以我们可以统计每一个值的贡献
即,(作为最大值的次数-作为最小值的次数)*高度
如何求作为最大值的次数?
我们可以求解,向左走第一个比他大的索引,向右走第一个比他大的索引
那么,在这个区间内。他就是最大值!
利用单调栈可以很容易地统计出来!
然后我们可以用同样的方法统计出最小值的次数
但是哇,我们这样有一个bug
就是,这个区间内有重复的数,我们统计时可能会有区间被重复选取!
那么该怎么办呢?
学到了!
我们可以在单调栈判断时,对于左边我们取等,对于右边我们不取等!
真的巧妙!
#include<iostream> #include<algorithm> #include<vector> using namespace std; typedef long long ll; const int max_n = 1e6+100; const int inf = 1e9; int h[max_n],lft[max_n],rgt[max_n]; int n; int main(){ ios::sync_with_stdio(0); while (cin>>n){ for (int i=1;i<=n;++i)cin>>h[i]; vector<int> stack; stack.push_back(0); h[n+1]=h[0]=inf; for (int i=1;i<=n;++i){ while (h[stack.back()]<=h[i])stack.pop_back(); lft[i]=i-stack.back(); stack.push_back(i); } stack.clear(); stack.push_back(n+1); for (int i=n;i>=1;--i){ while (h[stack.back()]<h[i])stack.pop_back(); rgt[i]=stack.back()-i; stack.push_back(i); } ll ans = 0; for (int i=1;i<=n;++i)ans+=1LL*lft[i]*1LL*rgt[i]*1LL*h[i]; stack.clear(); h[0]=h[n+1]=0; stack.push_back(0); for (int i=1;i<=n;++i){ while (h[stack.back()]>=h[i])stack.pop_back(); lft[i]=i-stack.back(); stack.push_back(i); } stack.clear(); stack.push_back(n+1); for (int i=n;i>=1;--i){ while (h[stack.back()]>h[i])stack.pop_back(); rgt[i]=stack.back()-i; stack.push_back(i); } for (int i=1;i<=n;++i)ans-=1LL*lft[i]*1LL*rgt[i]*1LL*h[i]; cout<<ans<<endl; } }