K 思维

思路

一个 part-k-bag 一定是由 “零个或多个 k-bag” + “不含 k-bag 的 part-k-bag” 组成

下称 “零个或多个 k-bag” 为 k-bags, “不含 k-bag 的 part-k-bag” 为 exclude-k-kag

  1. 我们先维护 exclude-k-bag 从左端和从右端的最长延申范围 [1, r), (l, n]，如果区间 [r + 1, l - 1] 的长度为 0，那么这个序列不存在 k-bags，但是它是一个 part-k-bag，因为它的左右两端形成两个 exclude-k-bag

  2. 如果区间 [r + 1, r - l] 的长度不为 0, 如果序列为 part-k-bag，那么一定存在 k-bags 跨过这个区间，我们使用双指针维护区间长度，找到合适的区间为止。如果找不到合适区间，那么它一定不是 part-k-bags

时间复杂度: $O(n)$

代码

#include <bits/stdc++.h>
 
using namespace std;
const int N = 5e5 + 5;
 
unordered_map<int, int> mp;
int a[N], vis[N];
 
int find_furthest(int from, int to, int step) {
    mp.clear();
    for (int i = from; i != to; i += step)
        if (++mp[a[i]] > 1)
            return i;
    return to;
}
  
bool solve(int n, int k) {
    int lr = find_furthest(0, n, 1);
    int rl = find_furthest(n - 1, lr - 1, -1);
    if (rl - lr + 1 <= 0) return true;
    else if (rl - lr + 1 < k) return false;
 
    memset(vis + 1, 0, sizeof(int) * n);
    // len: the length of longest k-bag
    // siz: the number of element equal to len
    int siz = 0, len = 0, tail = 0;
    for (int i = 0; i < n; ++i) {
        while (vis[a[i]] > len) {
            if (--vis[a[tail]] == len) --siz;
            tail++;
        }
        if (vis[a[i]]++ == len) ++siz;
        if (siz == k) {
            len++, siz = 0;
            if (tail <= lr && i >= rl) return true;
        }
    }
    return false;
}
  
int main() {
    int t, n, k;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &k);
        for (int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        puts(solve(n, k) ? "YES" : "NO");
    }
    return 0;
}