题库链接：
https://nanti.jisuanke.com/t/41387
题目大意
给定n个数，与一个数m，求ai右边最后一个至少比ai大m的数与这个数之间有多少个数
思路
对于每一个数，利用二分的方法求他右边大于等于ai+m的数的最后一个值。
关键在于怎么二分呢？
利用线段树存储区间最大值，看这个区间的最大值是不是比ai+m大
代码：
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define mod 1000000007
int a[maxn];
struct node
{
int l,r,ma;
}tree[maxn*];
void build(int l,int r,int p)
{
tree[p].l = l;
tree[p].r = r;
tree[p].ma = -;
if(l == r)
{
tree[p].ma = a[l];
return;
}
int mid = (l+r)/;
build(l,mid,p*);
build(mid+,r,p*+);
tree[p].ma = max(tree[p*].ma,tree[p*+].ma);
}
int query(int x,int y,int p)
{
if(x == tree[p].l && y == tree[p].r)
return tree[p].ma;
int mid = (tree[p].l + tree[p].r)/;
if(x > mid)
return query(x,y,p*+);
else if(y <= mid)
return query(x,y,p*);
else
return max(query(x,mid,p*),query(mid+,y,p*+)); }
int main()
{
int T,i,j,k,n,q,x,y,m,s,l,r,mid;
scanf("%d%d",&n,&m);
for(i=;i<=n;++i)
scanf("%d",&a[i]);
build(,n,);
for(i=;i<n;i++)
{
s=m+a[i];
l=i+;
r=n;
while(l<r)
{
mid=(l+r+)/;
if(query(mid,r,)>=s)
{
l=mid;
}
else if(query(l,mid,)>=s)
{
r=mid-;
}
else
{
break;
}
}
if(a[l]>=s)
cout<<l-i-<<' ';
else
cout<<"-1"<<' ';
}
cout<<"-1"<<endl;
return ;
}