参考博客
待读：树状数组做法
每日好文：权值线段树
题意：

给定n，k，d，表示给你n支铅笔，每支有一个权值v。现在让你把n支笔放入一些盒子中（盒子数量可以无穷大），每个盒子中至少有k支笔，而且每个盒子中的笔的max(v)-min(v)不超过d。问你能否找到一个合法的放法，可以输出”YES”，否则输出”NO”。

思路：

因为对权值差有要求，所以先进行排序，排序后能放进一个盒子的笔的权值v一定是连续的。之后记录两个值，一个是can[i]，表示第i支笔能否作为某一段的终点，另一个是st[i]，表示第i支笔能否作为某一段的起点。如果某支笔能作为某一段的终点，那么下一支笔一定可以当做某一段的起点，最后判断最后一支笔能否作为某一段的终点（即can[n]==1是否成立）。这样可以用尺取法（即two pointers）解决：将某一段的起点定为s，终点定为e，如果①起点所在位置可以作为某一段的起点（即st[s]==1成立）；②终点到起点的距离大于等于k（即e-s+1>=k）；③这一段的最大值减最小值不超过d（因为从小到大排序，所以最大值减最小值不超过d等价于a[e]-a[s]<=d）这三点成立，那么说明以s为起点，e为终点是可行的，则可以把can[e]赋值为1，把st[e+1]赋值为1。在①满足的情况下，直到③不满足之前，一直把e右移（即尺取法的思想）。

AC：code

#include<bits/stdc++.h>
using namespace std;
int a[612345];
int st[612345],ed[612345];
int main()
{

    int n,k,d;
    cin>>n>>k>>d;
    for(int i=1; i<=n; i++)scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    ed[0] = 1;
    st[1] = 1;
    int e =1;
    for(int s=1; s<=n; s++)
    {
        if(st[s]==1)
        {

            while(e<=n&&a[e]-a[s]<=d)
            {
                if(e-s+1>=k)
                {
                    ed[e] = 1;
                    st[e+1] = 1;
                }
                e++;
            }

        }

    }

if(ed[n]==1)
{
    cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
return 0;
}