XKC's basketball team（2019徐州站网络赛E线段树）

本文主要是介绍XKC's basketball team（2019徐州站网络赛E线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：题目链接嘤嘤嘤
一开始以为是主席树，想明白了之后线段树就可以。从后往前遍历，线段树二分查找离这个数最远的数字。返回那个数的下标。这个数查找完了就把这个数插入到线段树里。
代码如下：

#include<bits/stdc++.h>
#define ll long long
using 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) return 0;int L=p[cur].l;int R=p[cur].r;if(L==R) return L;int ans=0;if(p[cur<<1|1].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':' ');}
}