题意：
一个序列被称为k-bag，当且仅当序列由多个1到k的排列顺序连接
例如1,2,3, 2,1,3 ,3,2,1 是一个3-bag序列，因为可以拆分为{1,2,3}{2,1,3}{3,2,1}
给定长度为n的序列a，和一个整数k。
判断该序列是否可能是k-bag序列的某个子区间
数据范围：n=5e5，k=1e9，1=a(i)=1e9
解法：
设ma为序列的最大值，当mak的时候显然不是。
如果满足条件，那么这个序列一定是x p p p x的形式，其中p表示1到k的排列，x表示前后两端长度k的一段，
且前后两端的x一定没有重复数字
因为x的长度k，那么在[1,min(n,k)]范围内枚举左端x的长度，然后判断后面每一段长度为k的区间是否是排列，
以及末尾一段x是否所有数只出现一次，如果全都满足，则说明这个序列是k-bag。
那么问题就变为判断长度为k的区间是否是排列，和不满长度k的区间是否所有数只出现一次。
这个问题是经典题了，可以用last(i)表示a(i)上一次出现的位置，
对last建线段树，如果[l,r]中的最大值l，说明每种数都只出现一次。
当k=n的时，只需要查询[1,n]是否所有数只出现一次即可，只有一次查询，复杂度为log(n)
当kn的时，xpppx 一共k/n段，枚举左端x的长度次数为O(k)，总查询次数为n/k*k=n，加上线段树复杂度为nlog(n)
code：
#includebits/stdc++.h
using namespace std;
const int maxm=5e5+5;
int last[maxm];
int a[maxm];
int n,k;
struct ST{
int a[maxm2];
void pushup(int node){
a[node]=max(a[node*2],a[node*2+1]);
}
void build(int l,int r,int node){
if(l==r){
a[node]=last[l];
return ;
}
int mid=(l+r)/2;
build(l,mid,node*2);
build(mid+1,r,node*2+1);
pushup(node);
}
int ask(int st,int ed,int l,int r,int node){
if(st=led=r)return a[node];
int mid=(l+r)/2;
int ans=0;
if(st=mid)ans=max(ans,ask(st,ed,l,mid,node*2));
if(edmid)ans=max(ans,ask(st,ed,mid+1,r,node*2+1));
return ans;
}
}t;
signed main(){
int T;scanf("%d",T);
while(T--){
scanf("%d%d",n,k);
int ma=0;
for(int i=1;i=n;i++){
scanf("%d",a[i]);
ma=max(ma,a[i]);
}
if(mak){
puts("NO");continue;
}
unordered_mapint,intpre;
for(int i=1;i=n;i++){
last[i]=pre[a[i]];
pre[a[i]]=i;
}
t.build(1,n,1);
int ok=0;
for(int i=1;i=ki=n;i++){
if(t.ask(1,i,1,n,1)=1)break;
int okk=1;
for(int l=i+1;l=n;l+=k){
int r=min(l+k-1,n);
if(t.ask(l,r,1,n,1)=l){
okk=0;break;
}
}
if(okk){
ok=1;break;
}
}
if(ok)puts("YES");
else puts("NO");
}
return 0;
}
