题目描述

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

输入描述

  The first line contains one integer , denoting the number of test cases. Then TT test cases follow.
  The first line of each test case contains two integers .
  The second line of each test case contains integers indicate the sequence.
  It is guaranteed that , the values of the sequence are between and .

输出描述

  One line of each test case, if the sequence is a part--bag sequence, print "YES", otherwise print "NO".

示例1

输入

1
8 3
2 3 2 1 3 3 2 1

输出

YES

分析

  设给出的序列为 。
  首先，若 ，那么给出的 必然不是 part--bag，可以直接输出 “NO”。接下来的讨论皆基于 ， 的情况。
  若 各个元素互不相同，那么 可能恰好是 的全排列，也可能是一个 的全排列的一个子序列；根据 -bag 的定义，此时的 必然是个 part--bag。
  若 ，那么情况就类似样例 。 的头和尾是 的全排列的一部分，而中部是多个 的全排列。显然，对于 和 ，若 ，那么两者必然不会在同一个排列中。令 为满足 且 的最小整数，即 。那么 头部的结尾位置最大为 ，否则 的头部包含两个相同的数，不满足排列的定义。从 到 枚举 的头部结尾，每次检验接下来的序列是否能构成多个 的全排列即可，当然，检验时， 的尾部是很好识别的。为了做到 的时间复杂度，可以采用双指针。定义两个指针 ， 表示当前 头部结尾的位置。最初 ， 从 开始，不停地向后找 的全排列，因此可 理解为当前尚未检验过的序列的开头。维护 表示 在当前考察序列（当前考察序列指 这部分序列）内出现的次数； 的中部会有多个全排列，用 表示当前正在检验的全排列的编号，从 开始记录。假设已经检验完 个全排列，当前正在检验第 个全排列，由于 表示还未检验到的序列开头，那么当且仅当 时，前面有 个全排列；否则，说明当前的 作为头部的结尾不能使 成为 part--bag，应当继续枚举 。若 一直枚举到 还未找到 成为 part--bag 的方案，那么 就不是 part--bag。
  注意要用 和 ， 和 则容易超时。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第六场） Problem K
Date: 8/27/2020
Description: Double Pointer
*******************************************************************/
#include<unordered_map>
#include<cstdio>
#include<iostream>
#include<unordered_set>
using namespace std;
const int N=500004;
int _;
int a[N];
int n,k;
int main(){
    for(cin>>_;_;_--){
        scanf("%d%d",&n,&k);
        int i;
        bool flag=0;
        for(i=1;i<=n;i++){
            scanf("%d",a+i);
        }
        for(i=1;i<=n;i++){
            //超出范围
            if(a[i]<1||a[i]>k){
                flag=1;
                break;
            }
        }
        if(flag){
            puts("NO");
        }else{
            unordered_set<int>ex;
            int d;
            for(i=1;i<=n;i++){
                if(ex.count(a[i])){
                    //保证d是满足条件的最小整数
                    d=i;
                    break;
                }else{
                    ex.insert(a[i]);
                }
            }
            if(ex.size()==n){
                //互不相同的n个数
                puts("YES");
            }else{
                bool is=1;
                int l=1,r=2;
                int ID=1;//当前要找的全排列编号
                int num=0;//一个全排列中已经遍历的数字个数
                unordered_map<int,int>cnt;
                while(r<=n){
                    if(l==d){
                        is=0;
                        break;
                    }
                    bool find_permutation=1;
                    while(r<=n){
                        //若r能一直检验到n
                        //那么这个l就是合法的
                        if(cnt[a[r]]==ID-1){
                            //a[r]可以在第ID个排列内
                            cnt[a[r]]++;
                            r++;
                            num++;
                            if(num==k){
                            //找到一个全排列
                            //继续找下一个
                                num=0;
                                ID++;
                            }
                        }else{
                            //减去贡献
                            num--;
                            cnt[a[l+1]]--;
                            l++;
                            break;
                        }
                    }
                }
                puts(is?"YES":"NO");
            }
        }
    }
    return 0;
}