k bag

A sequence is called kk-bag, if and only if it is put in order by some (maybe one) permutations of 11 to kk. For example, 1,2,3,2,1,3,3,2,11,2,3,2,1,3,3,2,1 is a valid 33-bag sequence.
Roundgod is not satisfied with kk-bag, so she put forward part-kk-bag, which is a contiguous subsequence of kk-bag.
Wcy wants to know if the sequence of length nn is a part-kk-bag sequence.

题意：
k-bag：多个1-k排列连接起来的序列。判断一个序列是否是一个k-bag序列的子序列
魔幻题目，考场上写了个寂寞
参考https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44411696
真是写的又短又清晰呐...

#include<bits/stdc++.h>
using namespace std;
int a[5000050],f[500050];//f数组记录该位置可不可以切
unordered_map<int,int> mp;//可以用离散化代替
int main (){
int T;
scanf("%d",&T);
while(T--){
    mp.clear();
    int n,flag=0,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
        if(a[i]>k) flag=1;
    }
    if(flag){
        printf("NO\n");
        continue;
    }
    memset(f,0,sizeof(f));
    int cnt=0; f[0]=1;
    for(int i=1;i<=n;++i){
        if(i>k){
            mp[a[i-k]]--;
            if(mp[a[i-k]]==0) cnt--;//统计区间内的不同元素的个数
        }
        if(mp[a[i]]==0) ++cnt;
        mp[a[i]]++;
        if(cnt==k||cnt==i) f[i]=i-k>=0?f[i-k]:1;// 如果区间内有k（或者i个）个不同的数字说明该点可以用于切割
    }
    mp.clear(); cnt=0;//清空
    for(int i=n;i>=max(n-k,0);--i){
        if(f[i]&&cnt==n-i){
            flag=1; break;
        }//从后往前看，判断这个点是否可以切割，且该点从后面开始是否可以切割。若可以切割说明存在这种方案满足该序列是一个part k-bag。
        if(mp[a[i]]==0) cnt++;
        mp[a[i]]++;//统计区间内不同元素的个数
    }
    if(flag) printf("YES\n");
    else printf("NO\n");
    }
}