2020牛客多校第六场K题题解

比赛的时候是队友写的，用ST表实现了一下。
首先想到，枚举所有可能的区间划分方法，只要存在一种划分使得每个区间里的数字恰好出现一次即可，因为区间里1~k都要出现，也就相当于求是否存在一个出现了两次及以上的数字。
用一个数组记录每个数字和左边最近的与它相同的数字的下标。每次查询区间的最大值，如果最大值大于等于区间的左端点，说明存在一个数，在这个区间里出现了至少两次。此时的划分方法就是不合法的。

#include<bits/stdc++.h>
using namespace std;
const int N=2000007;
int t,n,k,a[N],st[N][20],f[N],lg[N];
void init_st(){
    for(int i=1;i<=n;++i)st[i][0]=i;
    for(int j=1;j<20;++j)for(int i=1;i<=n;++i){
        if(f[st[i][j-1]]>f[st[i+(1<<(j-1))][j-1]])st[i][j]=st[i][j-1];
        else st[i][j]=st[i+(1<<(j-1))][j-1];
    }
}
int rmq(int l,int r){
    return max(f[st[l][lg[r-l+1]]],f[st[r-(1<<lg[r-l+1])+1][lg[r-l+1]]]);
}
bool check(){
    for(int i=1;i<=min(n,k);++i){
        bool flag=1;
        if(rmq(1,i))continue;
        for(int j=i+1;j<=n;j+=k)if(rmq(j,min(n,j+k-1))>=j)flag=0;
        if(flag)return 1;
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    for(int i=2;i<N;++i)lg[i]=lg[i/2]+1;
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i=1;i<=n;++i)cin>>a[i];
        map<int,int> M;
        for(int i=1;i<=n;++i){
            f[i]=M[a[i]];
            M[a[i]]=i;
        }
        init_st();
        if(check())cout<<"YES"<<endl;else cout<<"NO"<<endl;
    }
    return 0;
}