XKC's basketball team(线段树)

XKC's basketball team

题意：

• 每个数在其右边找出比这个数大的数，数最右位置与数的距离

思路：

• 线段树找出区间的最大值，先比较一个区间的右子树，在比较区间的左子树

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=5*1e5+10;
int a[M];
struct node
{
    int l,r;
    int val;
    int id;
}tree[M<<2];
void pushup(int root)
{
    tree[root].val=max(tree[root<<1].val,tree[root<<1|1].val);
}
void build(int l,int r,int root)
{
    tree[root].l=l;
    tree[root].r=r;
    tree[root].val=0;
    if(l==r)
    {
        scanf("%d",&tree[root].val);
        a[l]=tree[root].val;
        tree[root].id=l;
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,root<<1);
    build(mid+1,r,root<<1|1);
    pushup(root);
}
int query(int root,int val)
{
    if(tree[root].l==tree[root].r)
    {
        return tree[root].id;
    }
    if(tree[root<<1|1].val>=val)
    {
        return query(root<<1|1,val);
    }
    else if(tree[root<<1].val>val)
    {
        return query(root<<1,val);
    }
    else
    {
        return -1;
    }
}
int main( )
{
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i=1;i<=n;i++)
    {
        int id=query(1,a[i]+m);
        if(id>i)
        {
            printf("%d%c",id-i-1,i==n?'\n':' ');
        }
        else
        {
            printf("-1%c",i==n?'\n':' ');
        }
    }
    return 0;
}