XKC's basketball team【线段树查询】

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

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

We define the anger of the ii-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 .

Please calculate the anger of every team member .

Input

The first line contains two integers nn and 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 nn integers w_1..w_n(0\leq w_i \leq 10^9)w1..wn(0≤wi≤109) .

Output

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

样例输入复制

6 1

3 4 5 6 2 10

样例输出复制

4 3 2 1 0 -1

题目大意：
1.给出一个长度为n的数列，给出m的值。问在数列中从右到左第一个比 arr[i] + m 大的值所在位置与 arr[i] 的所在位置之间夹着多少个数。
解题思路：
1.用线段树来记录区间最大值，优先从右子树开始查询是否存在大于 arr[i] + m的值，返回下标即该值在原数列中的位置，即可求得答案。
2.重要的是查询的值必须是在 i 的右边，否则输出 -1
代码如下：

 #include<stdio.h>

 #include<algorithm>

 using namespace std;

 const int MAXN = 5e5 + ;

 int n, m;

 int a[MAXN], ANS[MAXN];

 struct Tree

 {

     int val, l, r;

 }tree[ * MAXN];

 void build(int k, int l, int r)

 {

     tree[k].l = l, tree[k].r = r;

     if(l == r)

     {

         tree[k].val = a[l];

         return ;

     }

     int mid = (l + r) / ;

     build( * k, l, mid);

     build( * k + , mid + , r);

     tree[k].val = max(tree[ * k].val, tree[ * k + ].val);

 }

 int query(int k, int goal)

 {

     if(tree[k].l == tree[k].r)

         return tree[k].l;

     if(tree[ * k + ].val >= goal)

         return query( * k + , goal);

     else if(tree[ * k].val >= goal)

         return query( * k, goal);

     else

         return -;

 }

 int main()

 {

     scanf("%d%d", &n, &m);

     for(int i = ; i <= n; i ++)

         scanf("%d", &a[i]);

     build(, , n); //线段树建树

     for(int i = ; i <= n; i ++)

     {

         int flag = ;

         int ans = query(, a[i] + m); //由右边开始查询，返回右边第一个大于 a[i] + m值的位置

         if(ans == - || ans <= i)

             ANS[i] = -;

         else if(ans > i)

             ANS[i] = ans - i - ;

     }

     printf("%d", ANS[]);

     for(int i = ; i <= n; i ++)

         printf(" %d", ANS[i]);

     printf("\n");

     return ;

 }

巴特西

XKC's basketball team【线段树查询】

Input

Output

样例输入复制

样例输出复制

最新文章

热门文章