91 . B. Queue (灵茶每日一题 : 01-23)

链接 :?

Problem - B - Codeforces

思路 :

预处理后缀数组，存后面最小的值 ；

?然后二分 ；

代码 :?

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
typedef long long LL;
const int mod = 1e9+7;
const int N = 1e5+10;

using namespace std;

int n ;
int a[N] , sa[N];

int solve(int x){
	int l=x,r=n,ans=x;
	while(l<=r){
		int mid=l+r>>1;
		if(sa[mid]>=a[x])r=mid-1;
		else{
			ans=mid,l=mid+1;
		}
	}
	return ans-x-1;
}
 
int main()
{
	scanf("%d",&n);
	sa[n+1]=1000000010;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=n;i>=1;i--) sa[i]=min(a[i],sa[i+1]);
	for(int i=1;i<=n;i++){
		printf("%d ",solve(i));
	}
    return 0;
}