题目大意

若一个数列是由一些1∼k的排列组成，那么就被称作一个k-bag。例如，数列1,2,3,2,3,1,1,3,2是一个3−bag（由1,2,3 2,3,1 1,3,2三个排列组成）。
判断一个数列是不是一个k−bag的一部分。

解题思路

以样例2,3,2,1,3,3,2,1为例，可以发现，在前面补一个1，就可以构成正确的k−bag，所以这是k-bag的一部分。

  1. 可以先考虑最暴力的方式。如果有两个连续的相同数字（如上方3,3），那么这里就一定是一个分隔点。
    我们枚举每个分割点，每隔k位再设置一个分割点，挨个子区间枚举。但是这种方法显然还不够快。我们可以直接扫描，遇到端点相同的区间，就判断是否与之前矛盾。
    问题就是，怎样更高效地判断？

  2. 因为枚举的是可以设置分割点的区间，分割点k格一个，所以把这个区间向前移动（k的倍数）格本质上没有区别。
    因此，可以将所有的区间向前移动，一次k格，与其他区间出现交集，即判定合法。

  3. 但是我们需要考虑两端的交集，这又是一个问题。
    我们可以将一个区间的左端点+1，右端点右边的位置-1，然后求前缀和。这样可以得到，每个位置的数值就是重叠在上面区间的个数。
    最后找一下有没有数值是等于区间数的就可以了。

由于k过大，我们还需使用离散化处理。

AC代码

#include <bits/stdc++.h>
using namespace std;
int a[500010],b[500010],c[500010],d[500010],n,k;
int main(){
    int t,x,y,cnt,i,j;
    bool flag;
    scanf("%d",&t);
    while (t--)
    {
        x=1,y=0,flag=0;
        scanf("%d%d",&n,&k);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        sort(b+1,b+n+1);
        cnt=unique(b+1,b+n+1)-b-1;
        for(i=1;i<=n;i++) 
            a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
        for(i=1;i<=n;i++)
        {
            while(!c[a[x]] && x<=n)
                c[a[x]]++,x++;
            c[a[i]]--;
            d[i]=x-i;
        }
        for(i=1;i<=min(k,d[1]+1);i++)
        {
            flag=1;
            for(j=i;j<=n;j+=k)
            {
                if(j+d[j]>=n+1) continue;
                else if(d[j]^k)
                {
                    flag=0;
                    break;
                }
            }
            if(flag)
            {
                y=1;
                break;
            }
        }
        if(y) puts("YES");
        else puts("NO");
    }
}