K 思维

思路

一个 Part-K-Bag 一定是由 "零个或多个 K-Bag" + "不含 K-Bag 的 Part-K-Bag" 组成。

为方便起见，下称 "零个或多个 K-Bag" 为 K-Bags, "不含 K-Bag 的 Part-K-Bag" 为 Exclude-K-Bag。

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

时间复杂度:

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;

unordered_map<int, int> mp;
int a[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, -1, -1);
    if (rl - lr + 1 <= 0) return true;

    mp.clear();
    // 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 (mp[a[i]] > len) {
            if (--mp[a[tail]] == len) --siz;
            tail++;
        }
        if (mp[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;
}