The Preliminary Contest for ICPC Asia Xuzhou 2019 E. XKC's basketball team

题目链接：https://nanti.jisuanke.com/t/41387

思路：我们需要从后往前维护一个递增的序列。

因为：我们要的是wi + m <= wj,j要取最大，即离i最远的那个j，每次索引一个wi都需要判断下是不是大于w(i+1)，完成递增序列的维护。

代码里面能更好的理解为什么要维护一个递增的序列

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <cmath>
using namespace std;
 
typedef long long LL;
#define inf 1e9
#define rep(i,j,k) for(int i = (j); i <= (k); ++i)
#define rep__(i,j,k) for(int i = (j); i < (k); ++i)
#define per(i,j,k) for(int i = (j); i >= (k); --i)
#define per__(i,j,k) for(int i = (j); i > (k); --i) 

const int N = (int)5e5 + 10;
int arr[N];
int ans[N];

struct node{
    int index;
    int w;
    
    void set(int x,int y){
        index = x;
        w = y;
    }
}que[N];

int main(){

    int n,m;
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d",arr+i);

    int l,r,mid,A;
    int len = 0;
    //最后一个先处理
    que[++len].set(n,arr[n]);
    ans[n] = -1;
    //
    per(i,n-1,1){

        //比之前的都大
        if(arr[i] + m > que[len].w){ 
            ans[i] = -1;
            if(arr[i] > que[len].w)
                que[++len].set(i,arr[i]);
        }
        //比第一个还小
        else if(arr[i] + m <= que[1].w){
            ans[i] = que[1].index - i -1;
            // printf("this is %d test  ans is %d \n",i,ans[i]);
        }
        //在中间有答案
        else{
            l = 1;
            r = len;
            while(l <= r){
                mid = (l + r) >> 1;
                if(arr[i] + m <= que[mid].w){
                    A = que[mid].index;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
  //          printf("arr[%d] = index %d - index %d - 1\n",i,A,i);
            ans[i] = A - i -1;
        }        
    }

    // rep(i,1,ll) printf("%d ",que[i].index);
    // printf("\n");

    printf("%d",ans[1]);
    rep(i,2,n) printf(" %d",ans[i]);
    printf("\n");

    getchar(); getchar();
    return 0;
}