题面:
题意:
判断一个序列是不是由若干个 [1...k] 的全排列拼接而成的序列的连续子序列。
题解:
我们先求出每个位置 pos 往前 k 个数有没有可能是一个全排列。
然后再求出每个位置 pos 往后 k 个数有没有可能是一个全排列。
给定序列的构成一定是 一个全排列的一部分+若干个全排列+一个全排列的一部分,其中这三部分均可能为空。
我们枚举序列起始多少个数是某个全排列的一部分即可。
因为若已经确定序列起始某些数是某个全排列的一部分,那整个序列的构成即可确定。
时间复杂度 O(n),因为每个位置只会被检查一次。
但是离散化的时间复杂度是 O(nlogn),所以总时间复杂度 O(nlogn)。
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=500100;
const int maxp=400100;
const int maxm=600100;
const int up=200000;
bool hal[maxn],har[maxn];
int mp[maxn];
int a[maxn],b[maxn];
int main(void)
{
int tt;
scanf("%d",&tt);
while(tt--)
{
int n,k;
bool flag=false;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>k) flag=true;
hal[i]=har[i]=false;
b[i]=a[i];
mp[i]=0;
}
sort(b+1,b+n+1);
int now=unique(b+1,b+n+1)-(b+1);
for(int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+now+1,a[i])-b;
if(flag)
{
printf("NO\n");
continue;
}
int cnt=0;
for(int r=1,l=1;r<=n;r++)
{
mp[a[r]]++;
if(mp[a[r]]==2) cnt++;
while(r-l+1>k)
{
mp[a[l]]--;
if(mp[a[l]]==1) cnt--;
l++;
}
if(cnt==0) hal[r]=true;
}
for(int i=1;i<=n;i++)
mp[i]=0;
cnt=0;
for(int r=n,l=n;l>=1;l--)
{
mp[a[l]]++;
if(mp[a[l]]==2) cnt++;
while(r-l+1>k)
{
mp[a[r]]--;
if(mp[a[r]]==1) cnt--;
r--;
}
if(cnt==0) har[l]=true;
}
hal[0]=true;
har[n+1]=true;
bool fl=false;
for(int i=0;i<=n&&i<k;i++)
{
bool ok=true;
for(int j=i;j<=n;j+=k)
{
if(hal[j]==false)
{
ok=false;
break;
}
}
if(har[(n-i)/k*k+1+i]==false) ok=false;
if(ok==true)
{
fl=true;
break;
}
}
if(fl) printf("YES\n");
else printf("NO\n");
}
return 0;
}