网址：https://nanti.jisuanke.com/t/41387
大家好，我是训练时长两年半的个人练习生蔡徐坤，我的爱好是唱，跳，rap，篮球。
给出一段长度为$n，(n \leq 1e5)$的序列，对每一个数，求出它和它后面比它大$m$的数中间夹着的数的数量，没有输出$-1$。
直接建线段树，维护最大值，然后查询时对第$i$个数，搜索区间$[i,n]$之中大于$num[i]+m$的值的位置的最大值，具体操作是先限定区间，然后求出所有合法位置，取最大值，如果搜索不到则返回$-1$，（注意考虑$m=0$的情况），剪枝的操作是如果区间最大值小于下界，就不用查找了，然后判断一下是否存在就好了。
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define ls (k<<1)
#define rs ((k<<1)+1)
const int MAXN = 5e5 + 5;
int num[MAXN];
struct segtree
{
struct node
{
int l, r;
long long val;
};
node tr[MAXN << 2];
void build(int l, int r, int k)
{
tr[k].l = l, tr[k].r = r;
if (l == r)
{
tr[k].val = num[l];
return;
}
int m = (l + r) >> 1;
build(l, m, ls);
build(m + 1, r, rs);
tr[k].val = max(tr[ls].val, tr[rs].val);
}
int query(int l, int r, int k, long long val)
{
//cout << tr[k].l << " " << tr[k].r << " " << tr[k].val << endl;
if (l <= tr[k].l && r >= tr[k].r)
{
if (tr[k].l == tr[k].r)
return tr[k].val >= val ? tr[k].l : -1;
int pos = -1;
//cout << "==" << tr[ls].val << " " << tr[rs].val << endl;
if (tr[rs].val >= val)
pos = max(pos, query(l, r, rs, val));
else if (tr[ls].val >= val)
pos = max(pos, query(l, r, ls, val));
else
pos = -1;
return pos;
}
int m = (tr[k].l + tr[k].r) >> 1;
int pos = -1;
if (l <= m)
pos = max(pos, query(l, r, ls, val));
if (r > m)
pos = max(pos, query(l, r, rs, val));
return pos;
}
};
segtree tr;
int main()
{
int n;
long long m;
scanf("%d%lld", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &num[i]);
tr.build(1, n, 1);
for (int i = 1; i <= n; ++i)
{
int pos = tr.query(i, n, 1, num[i] + m);
//cout << pos << endl;
if (pos == i || pos == -1)
printf("-1");
else
printf("%d", pos - i - 1);
printf("%c", i == n ? ‘\n‘ : ‘ ‘);
}
return 0;
}
2019徐州网络赛 XKC's basketball team 线段树
原文：https://www.cnblogs.com/Aya-Uchida/p/11489292.html