2019徐州网络赛K XKC's basketball team（结构体排序+二分+RMQ）

XKC , the captain of the basketball team , is directing a train of nnn team members. He makes all members stand in a row , and numbers them 1⋯n1 \cdots n1⋯n from left to right.

The ability of the iii-th person is wiw_iwi​ , and if there is a guy whose ability is not less than wi+mw_i+mwi​+m stands on his right , he will become angry. It means that the jjj-th person will make the iii-th person angry if j>ij>ij>i and wj≥wi+mw_j \ge w_i+mwj​≥wi​+m.

We define the anger of the iii-th person as the number of people between him and the person , who makes him angry and the distance from him is the longest in those people. If there is no one who makes him angry , his anger is −1-1−1 .

Please calculate the anger of every team member .

Input

The first line contains two integers nnn and m(2≤n≤5∗105,0≤m≤109)m(2\leq n\leq 5*10^5, 0\leq m \leq 10^9)m(2≤n≤5∗105,0≤m≤109) .

The following  line contain nnn integers w1..wn(0≤wi≤109)w_1..w_n(0\leq w_i \leq 10^9)w1​..wn​(0≤wi​≤109) .

Output

A row of nnn integers separated by spaces , representing the anger of every member .

样例输入复制

6 1
3 4 5 6 2 10

样例输出复制

4 3 2 1 0 -1

题意：

n个人排成一队，第i个人的能力为w[i],对于右侧能力值>=w[i]+m的人，第i个人会产生一个愤怒值，愤怒值为两人之间隔的人数。即输出每个人和距离他最远的能力>=w[i]+m的人的下标差

先按能力值结构体排序，然后二分查找右侧第一个能力>=w[i]+m的人

RMQ该人到最后的区间最大id值，存下来，再按id排序，输出

我太菜了 我不会写二分 我的妈啊

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+30;
ll n,m;
struct stu
{
    ll a,id,ans;

} s[N];

bool cmp1(stu x,stu y)
{
    if(x.a!=y.a)
        return x.a<y.a;
    else
        return x.id<y.id;
}

bool cmp2(stu x,stu y)
{
    return x.id<y.id;
}

ll dp[N][20];

void ST_prework()
{
    for(ll i=1; i<=n; i++)
        dp[i][0]=s[i].id;
    for(ll i=1,imax=log2(n); i<=imax; i++)
    {
        for(ll j=1; j+(1<<i)-1<=n; j++)
            dp[j][i]=max(dp[j][i-1],dp[j+(1<<i-1)][i-1]);
    }
}

ll ST_query(ll l,ll r)
{
    ll k=log2(r-l+1);
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}

int main()
{
    while(~scanf("%lld%lld",&n,&m))
    {
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&s[i].a);
            s[i].id=i;
        }
        sort(s+1,s+n+1,cmp1);
//        for(int i=1;i<=n;i++)
//            cout<<s[i].a<<' ';
//        cout<<'\n';
        ST_prework();
        for(int i=1; i<=n; i++)
        {
            ll l=i+1,r=n;
            while(l<r)
            {
                ll mid=(l+r)/2;
                if(s[i].a+m<=s[mid].a)
                    r=mid;
                else
                    l=mid+1;
            }
//            cout<<r<<endl;
            if(r>=1&&r<=n&&s[i].a+m<=s[r].a){
//                cout<<r<<' '<<m<<' '<<s[i].a<<' '<<i<<endl;
                s[i].ans=ST_query(r,n)-s[i].id-1;
                if(s[i].ans<-1)
                    s[i].ans=-1;
            }
            else
                s[i].ans=-1;
        }
//        cout<<'\n';
        sort(s+1,s+n+1,cmp2);
        for(int i=1; i<=n; i++)
        {
            cout<<s[i].ans;
            if(i<n)
                cout<<' ';
        }
        cout<<'\n';
    }
    return 0;
}