2020牛客暑期多校训练营（第六场）[K] K-Bag

K-Bag定义为K的多个任意全排列的组合（eg：1 2 3 2 3 1 1 2 3），给定一个长为n的数组，判断是否为K-Bag的一部分。

题解： (1≤n≤5⋅10⁵,1≤k≤10⁹)，k<=n时，用g[i]判断前i个数是否不相等，h[i]判断i~n是否不相等，f[i]判断i~i+k是否不相等，b[i]表示i出现次数，num表示当前区域出现超过1次的数的个数。

 　　　当k>n时，最多只会有两个段（…2 3 4 / 2 1 3…），离散化后判断。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<cstring> 
 5 #include<queue>
 6 using namespace std;
 7 int const N=5e5+10;
 8 int n,k;
 9 bool f[N],g[N],h[N];
10 int a[N],b[N];
11 bool find(int s){
12   int i;
13   for (i=s;i+k-1<=n;i+=k)
14     if (!f[i]) return false;
15   if (i<=n && !h[i]) return false;
16   return true;
17 }
18 void work(){
19   for (int i=1;i<=n;i++){
20     scanf("%d",&a[i]);
21     b[i]=0;
22     f[i]=false;
23     g[i]=false;  //前后缀 
24     h[i]=false;
25    }
26    int num=0;
27    for (int i=1;i<=k;i++){
28       b[a[i]]++;
29       if (b[a[i]]==2) num++;
30       if (num==0) g[i]=true;
31     }
32     if (num==0) f[1]=true;
33     for (int i=k+1;i<=n;i++){
34      b[a[i-k]]--;
35      if (b[a[i-k]]==1) num--;
36      b[a[i]]++;
37       if (b[a[i]]==2) num++;
38       if (num==0) f[i-k+1]=true;
39     }
40     for (int i=n-k+1;i<=n;i++){
41       b[a[i-1]]--;
42      if (b[a[i-1]]==1) num--;
43      if (num==0) h[i]=true;
44     }
45     g[0]=true;
46     for (int i=0;i<k;i++)
47       if (g[i] && find(i+1)) {
48         printf("YES
");
49         return;
50       }
51   printf("NO
");
52 }
53 void work2(){
54     for (int i=1;i<=n;i++){
55       scanf("%d",&a[i]);
56       b[i]=a[i];
57       g[i]=false;
58       h[i]=false;
59     }
60     sort(b+1,b+n+1);
61     int temp=unique(b+1,b+n+1)-b-1;
62     for (int i=1;i<=n;i++){
63       a[i]=lower_bound(b+1 , b+temp+1 , a[i]) - b;
64     }
65     for (int i=1;i<=n;i++)
66      b[i]=0;
67     int num=0;
68     for (int i=1;i<=n;i++){
69       b[a[i]]++;
70       if (b[a[i]]==2) num++;
71       if (num==0) g[i]=true;
72     }
73     for (int i=1;i<=n;i++){
74       b[a[i-1]]--;
75      if (b[a[i-1]]==1) num--;
76      if (num==0) h[i]=true;
77     }
78     g[0]=true;
79     h[n+1]=true;
80     for (int i=0;i<=n;i++)
81       if (h[i+1] && g[i]){
82        printf("YES
");
83         return;
84       }
85   printf("NO
");
86 }
87 int main(){
88   int t;
89   scanf("%d",&t);
90   while (t--){
91     scanf("%d%d",&n,&k);  //k<n 时 
92     if (k<=n) work();
93      else work2();
94   }
95 return 0;
96 }