题目描述

闲的胃疼的Roundgod定义了一种叫k-bag的序列，这类序列由若干个从1~k的排列依次排列组成，例如1,2,3,2,1,3,3,2,1就是一个有效的3-bag序列。
但Roundgod对k-bag序列感到不满意，于是又定义了part-k-bag。如果一个序列是一个k-bag的连续子串，那么这个序列就叫做part-k-bag序列。
现在需要判断一个序列是否是part-k-bag序列。

输入描述

第一行输入一个数据T，表示测试数据的数目；
每个测试数据的第一行输入两个数字n,k（， ）；
接下来一行输入n个整数，表示该序列，其中确保 ，每个整数在到 的范围内。

输出描述

输出一行，若该序列是part-k-bag序列，则输出“YES”，否则输出“NO”（只需输出引号内的内容，无须输出引号）。

样例

• 输入
  1
  8 3
  2 3 2 1 3 3 2 1
• 输出
  YES

题解思路

看到这个数据范围，而且这是看数组的，首先建议离散化。
怎么说呢，这个序列可以通过放“隔板”来分割成一个个1到k的排列或部分排列，而隔板之间就是一个个区间。
我们可以先求共有多少隔板，然后移动区间，是区间的左端点在0到k之间。然后左端点加一右端点减一并求前缀和，最后找一下有没有数恰好等于区间数。
当然，题中所给数据范围并没有说明序列中的数一定小于k，所以要特判，而且显然这种情况是不合法的。

官方题解：

参考代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=500500;
int n,k,a[MAXN],b[MAXN],pre[MAXN],sum[MAXN];

void disc()//离散化
{
    sort(b+1,b+1+n); int cnt=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        bool flag=1;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",a+i),b[i]=a[i];
            if(a[i]>k) flag=0;//特判
        }
        if(!flag){printf("NO\n");continue;}
        if(k>n) disc();
        memset(pre,0,sizeof(pre));
        memset(sum,0,sizeof(sum));
        int cnt=0,m=min(n+1,k);
        for(int i=1;i<=n;i++)
        {
            if(pre[a[i]]&&pre[a[i]]>i-k)
            {
                cnt++;//调整
                sum[pre[a[i]]%k]++;
                sum[i%k]--;
                if(pre[a[i]]%k>=i%k)
                {
                    sum[m]--;
                    sum[0]++;

                }
            }
            pre[a[i]]=i;
        }
        flag=0;
        for(int i=0;i<m;i++)
        {
            if(i)sum[i]+=sum[i-1];
            if(sum[i]==cnt)//查找
            {
                flag=1;
                break;
            }
        }
        if(flag)printf("YES\n");
        else printf("NO\n");
    }
}