2019徐州网络赛 - XKC's basketball team

题目链接：XKC’s basketball team

比较简单的做法就是线段树维护最大值，然后二分区间找最远的那一个即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e5+10;
int n,m,a[N],res[N];
struct node{
	int l,r,mx;
}t[N<<2];
inline void push_up(int p){
	t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
}
void build(int p,int l,int r){
	t[p].l=l;	t[p].r=r;	
	if(l==r){
		t[p].mx=a[l];	return ;
	}
	int mid=t[p].l+t[p].r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
	push_up(p);
}
int ask(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r)	return t[p].mx;
	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return ask(p<<1,l,r);
	else if(l>mid)	return ask(p<<1|1,l,r);
	else	return max(ask(p<<1,l,mid),ask(p<<1|1,mid+1,r));
}
signed main(){
	scanf("%d %d",&n,&m);	
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);	build(1,1,n);
	for(int i=1;i<n;i++){
		int k=a[i]+m;
		if(ask(1,i+1,n)<k){
			res[i]=-1;
		}else{
			int l=i+1;	int r=n;
			while(l<r){
				int mid=l+r+1>>1;
				if(ask(1,mid,r)>=k)	l=mid;
				else	r=mid-1;
			}
			res[i]=l-i-1;
		}
	}
	res[n]=-1;
	for(int i=1;i<=n;i++){
		if(i==1)	printf("%d",res[i]);
		else	printf(" %d",res[i]);
	}puts("");
	return 0;
}