本文共 1591 字，大约阅读时间需要 5 分钟。

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 13 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 
   
    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
    
     =1&&r<=n&&s[i].a+m<=s[r].a){//                cout<
     
      <<' '<
      
       <<' '<
       
        <<' '<
        <
       
      
     
    
   

转载地址：http://ngno.baihongyu.com/