CF91B Queue

Tx_Lcy · 2022-09-22 07:54:13 · 题解

题目传送门

思路

翻遍了所有题解发现没有像我这样的在单调队列上二分的思路。

考虑从右往左把数加入单调队列，如果当前的数比单调队列的队尾要大，显然不可能作为答案，因为明明有更右边且比它更小的数存在，所以不能加入单调队列。而如果当前的数比单调队列的队尾要小，显然可以加入单调队列，但是此时的答案是 -1，因为没有任何数比它小。

找答案的过程可以视为在单调队列上二分的过程，我们只需要找到第一个小于它的数即可。

代码

#include<bits/stdc++.h>
using namespace std;
int const N=1e5+10;
int a[N],ans[N];
struct node{int val,id;}q[N];
inline int find(int l,int r,int x){
    while (l<r){
        int mid=(l+r)>>1;
        if (q[mid].val<x) r=mid;
        else l=mid+1;
    }
    return q[l].id;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;cin>>n;
    for (int i=1;i<=n;++i) cin>>a[i];
    int top=0;
    for (int i=n;i>=1;--i)
        if (!top || a[i]<=q[top].val) ans[i]=-1,q[++top].val=a[i],q[top].id=i;
        else ans[i]=find(1,top,a[i])-i-1;
    for (int i=1;i<=n;++i) cout<<ans[i]<<' ';
    cout<<'\n';
    return 0;
}