简介
有时候，我们让 栈/队列 中的所有元素满足单调，然后处理会比较方便。
P2947 [USACO09MAR]Look Up S
给出一个长度为 \(N\) 的序列 \(A\)，求出一个序列 \(P\)，使得 \(P_i\) 为最大的 \(j\)，使得 \(j<i\) 且 \(A_j>A_i\)（若不存在，则 \(P_i=0\)）。输出 \(P\)。\(1 \leq N \leq 10^6\)。
首先显然存在 \(O(N^2)\) 暴力，可以拿到 \(92\) 分。然后考虑优化：
维护一个单调递增栈 \(S\)，存储位置，将不满足递增性质（即，\(\forall i,j(i<j) A_{S_i} <A_{S_j}\) ）的多余元素出栈，然后不难发现，栈顶就是答案。注意，如果是栈为空，那么答案是 \(0\)。
时间复杂度 \(O(N)\)。
参考代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
stack<int> sta;
int n,h[1000005];
int ret[1000005];
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i];
}
for(int i=n;i;i--){
while(!sta.empty()&&h[sta.top()]<=h[i]){
sta.pop();
}
ret[i]=((sta.empty())?0:sta.top());
sta.push(i);
}
for(int i=1;i<=n;i++){
cout<<ret[i]<<'\n';
}
return 0;
}
P2866 [USACO06NOV]Bad Hair Day S
给出一个长度为 \(N\) 的序列 \(h\)，你需要求出一个序列 \(C\) 使得 \(C_i\) 为所有满足 \(j<i\) 且 \(h_j>h_i\) 的 \(j\) 的个数。求 \(\sum\limits_{i=1}^{n}{C_i}\)。\(1 \leq N \leq 80000\)。
感觉这两道题的唯一区别就是一个求最近的，一个求总数。不难发现，\(C_i\) 就是求当前单调栈的大小。
时间复杂度 \(O(N)\)。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
stack<int> sta;
int n,h[1000005];
int ret;
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i];
}
for(int i=1;i<=n;i++){
while(!sta.empty() && h[sta.top()]<=h[i]){
sta.pop();
}
if(!sta.empty())ret+=sta.size();
sta.push(i);
}
cout<<ret;
return 0;
}