本文共 1227 字，大约阅读时间需要 4 分钟。
题目链接：
一开始以为是主席树，想明白了之后线段树就可以。从后往前遍历，线段树二分查找离这个数最远的数字。返回那个数的下标。这个数查找完了就把这个数插入到线段树里。
代码如下：
#include #define ll long longusing namespace std;const int maxx=5e5+100;struct node{ int l; int r; int sum;}p[maxx<<3];ll a[maxx];int ans[maxx];ll b[maxx];int n,m;inline int getid(ll x,int len){ return lower_bound(b+1,b+1+len,x)-b;}inline void pushup(int cur){ p[cur].sum=max(p[cur<<1].sum,p[cur<<1|1].sum);}inline void build(int l,int r,int cur){ p[cur].l=l; p[cur].r=r; p[cur].sum=0; if(l==r) return ; int mid=l+r>>1; build(l,mid,cur<<1); build(mid+1,r,cur<<1|1);}inline void update(int pos,ll v,int cur){ int L=p[cur].l; int R=p[cur].r; if(L==R) { p[cur].sum=v; return ; } int mid=L+R>>1; if(pos<=mid) update(pos,v,cur<<1); else update(pos,v,cur<<1|1); pushup(cur);}inline int query(ll v,int cur){ if(p[cur].sum =v) ans = query(v,cur<<1|1); if(ans==0) ans = query(v,cur<<1); return ans;}int main(){ while(~scanf("%d%d",&n,&m)) { int cnt=0; for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,n,1); for(int i=n;i>=1;i--) { int x=query(a[i]+m,1); ans[i]=x?x-i-1:-1; update(i,a[i],1); } for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' '); }}
努力加油a啊，(o)/~
转载地址：http://kktvi.baihongyu.com/