CF985E 题解

_edge_ · 2022-07-21 13:32:59 · 题解

大家好，我是暴力数据结构选手。

首先一看到这道题目，就应该要想到贪心，将其从小到大排序肯定是最优的，证明大概就是考虑如果一个中间的数被换出去，肯定不优。

脑子一抽就想到暴力 DP，然后用数据结构来维护掉。

具体的，设 f_i 表示 i 结尾的能不能分出来。

然后转移就是 f_i \leftarrow f_j \vee f_i 并且 a_i-a_{j+1}\le d 以及 i-j \ge k。

我们发现这两个限制条件都具有单调性，及对于 a_i 能到达的最远的 a_{j+1} ，a_{j+2} 也肯定满足所需要的条件，通过这一点，可以用二分来将最远的点搞出来。

对于第二个限制条件，可以计算最近的 j 满足条件，然后这个题目就变成了给定一个区间，求区间是否有 1。

然后这就是暴力树状数组或者线段树来维护就可以了。

时间复杂度 O(n \log n)。

我自己脑子一抽用了个 ST 表，但实际上根本不用。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF=5e5+5;
int n,k,d,a[INF],f[INF][25],f1[INF][25],lg[INF],ll[INF],ff[INF];
int query(int l,int r) {
    int len=lg[r-l+1];
    return max(f[l][len],f[r-(1<<len)+1][len]);
}
int query1(int l,int r) {
    int len=lg[r-l+1];
    return min(f1[l][len],f1[r-(1<<len)+1][len]);
}
int tree[INF];
void t_add(int x,int y) {for (int i=x;i<=5e5;i+=i&-i) tree[i]+=y;return ;}
int t_query(int x) {int sum=0;for (int i=x;i;i-=i&-i) sum+=tree[i];return sum;}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k>>d;
    for (int i=1;i<=n;i++) 
        cin>>a[i];
    sort(a+1,a+1+n);
    for (int i=1;i<=n;i++) 
        f[i][0]=a[i],f1[i][0]=a[i];
    for (int i=1;i<=25;i++) {
        if ((1<<i)>n) break;
        for (int j=1;j+(1<<i)-1<=n;j++) {
            f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
            f1[j][i]=min(f1[j][i-1],f1[j+(1<<(i-1))][i-1]);
        }
    }
    lg[0]=-1;
    for (int i=1;i<=n;i++)
        lg[i]=lg[i>>1]+1;
    ff[0]=1;
    for (int i=1;i<=n;i++) {
        int l=1,r=i,ans=-1;
        while (l<=r) {
            int Mid=(l+r)>>1;
            if (a[i]-a[Mid]<=d) r=(ans=Mid)-1;
            else l=Mid+1;
        }
        ll[i]=ans-1;
    }

    for (int i=k;i<=n;i++) {
        if (ll[i]==0) ff[i]=1;
        else {
            if (ll[i]>i-k) continue;
            int kk=t_query(i-k)-t_query(ll[i]-1);
            ff[i]=(kk>=1);
        }
        t_add(i,ff[i]);
//      cout<<i<<" "<<ff[i]<<" "<<ll[i]<<" overrrr\n";
    }
    if (ff[n]) cout<<"YES\n";
    else cout<<"NO\n";
    return 0;
}