Codeforces 91B 思维，栈_栈 codeforces-CSDN博客

本文链接：https://blog.csdn.net/stdforces/article/details/126818296

题意：

给出一个长度为 $n$ 的数组，令 $f (i)$ 为在区间 $[i, n]$ 内最远的且小于 $a_{i}$ 的元素的位置与 $i$ 位置之间有多少个元素，求 $f (1), f (2), ..., f (n)$

方法：

从右向左维护一个单调递减栈（因为我们是向右找所有小于我们的值）：当 $a [i] < a [s . t o p ()] ∣∣ s . e m pt y ()$ ，入栈，否则不入栈。

当 $a_{i}<a[s.top()]$ ，加入栈，并且 $an s [i] = - 1$ ，假设右边有一个值小于现在的 $a_{i}$ ，那么我们一定不可以进栈，与维护的栈矛盾，所以右边一定不存在有元素 $a_{i}$ ，因此 $an s [i] = - 1$

否则，此时不入栈，栈内的元素都是小于 $a_{i}$ 的元素，只需要在里面找出来最远的那个即可，因为有单调性，所以可以二分来找他。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int n,a[3000005],ans[200005],s[200005],cnt=200001;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    //找出比a[i]小的且最远的地方是哪里？
    for(int i=n;i>=1;i--)
    {
        if(cnt==200001||a[i]<a[s[cnt]])
        {
            s[--cnt]=i;
            ans[i]=-1;
        }
        else if(a[i]==a[s[cnt]]) ans[i]=-1;
        else
        {
            int pos=*(lower_bound(s+cnt,s+1+200000,i,[&](int x,int y){
                return a[x]<a[y];
            })-1);
            if(pos==0) pos=s[200000];
            ans[i]=pos-i-1;
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);
    return 0;
}