Inaccurate Subsequence Search

题目连接：

Problem - D - Codeforces

---

题目描述

Maxim 有一个由 $n$ 个整数组成的数组 $a$ 和一个由 $m$ 个整数组成的数组 $b$ ( $m \le n$ )。

如果数组 $c$ 中的元素可以重新排列，使得其中至少有 $k$ 个元素与数组 $b$ 中的元素匹配，那么马克西姆认为长度为 $m$ 的数组 $c$ 是好数组。

例如，如果 $b = [1, 2, 3, 4]$ 和 $k = 3$ ，那么数组 $[4, 1, 2, 3]$ 和 $[2, 3, 4, 5]$ 是好数组(它们可以按如下方式重新排列： $[1, 2, 3, 4]$ 和 $[5, 2, 3, 4]$ )，而数组 $[3, 4, 5, 6]$ 和 $[3, 4, 3, 4]$ 则不是好数组。

马克西姆希望选择长度为 $m$ 的数组 $a$ 的每个子段作为数组 $c$ 的元素。请帮助 Maxim 计算有多少个数组是好的。

换句话说，找出有多少个位置 $1 \le l \le n - m + 1$ 的元素 $a _ l, a _ {l+1}, \dots, a _ {l + m - 1}$ 构成了一个好的数组。

输入描述

第一行包含一个整数 $t$ $( 1 \le t \le 10^4 )$ - 测试用例数。

每个测试用例的第一行包含三个整数 $n$ 、 $m$ 和 $k$ ( $1 \le k \le m \le n \le 2 \cdot 10^5$ )–数组 $a$ 和 $b$ 中的元素个数，也就是所需的匹配元素个数。

每个测试用例的第二行包含 $n$ 个整数 $a _ 1, a _ 2, \dots, a _ n$ ( $1 \le a _ i \le 10^6$ )。( $1 \le a _ i \le 10^6$ ) - 数组 $a$ 的元素。数组 $a$ 中的元素不一定是唯一的。

每个测试用例的第三行包含 $m$ 个整数 $b _ 1, b _ 2, \dots, b _ m$ ( $1 \le b _ i \le 10^6$ ) - 数组 $b$ 的元素。数组 $b$ 中的元素不一定是唯一的。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$ 。同样，保证所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$ 。

输出描述

对于每个测试用例，另起一行输出数组 $a$ 中良好子段的数量。

示例

输入

text

5
1 1 1 0
1 0 1 2
2 2 2 0
3 3 2 0
0 9 9 9

输出

text

1
1
3
3
12

说明

在第一个例子中，所有分段都很好。

在第二个示例中，好的子线段从位置 $1$ 、 $2$ 和 $3$ 开始。

在第三个示例中，好的子线段从位置 $1$ 和 $2$ 开始。

---

题解

按照题目意思，我们需要从左到右依次从 $a$ 中取与 $b$ 等长的数组来判断这个数组是否为 “好线段” 。这道题的关键点在于怎么计算一个数组与 $b$ 数组的相同个数。，显然，每次都对取出的数组进行计数时间开销过大。所以我们选择额外开一个数组，这个数组的下标即为 $b$ 中元素的值，我们在输入 $b$ 的值的时候就将 $b$ 的值记入下来，每出现一个值就将对应的下标的值加 $1$ 。

我们再来思考一个问题，如果 $a$ 数组为 $[1,1,1,1]$ ，b数组为 $[1,2,3]$ ，我们要求的 $k$ 为 $3$ ，这个时候按我们之前的设想得出的答案是 $2$ ，显然这个答案是错误的。这个时候我们需要再用一个数组来维护当前数组每个数字出现的次数，并于之前的进行比较，得出最后答案。

至于怎么从 $a$ 数组 中取与 $b$ 数组等长的子数组，当然是使用双指针了，这里其实还有另外一个叫法：“滑动窗口”。

下面给出完整代码：

#include <bits/stdc++.h>
using namespace std;

int a[200005] = {0};
int b[200005] = {0};

void solve()
{
    map<int, int> c; // 用于判断a是否在b中出现
    map<int, int> d; // 用于判断b中某个数的个数是否超过限制
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++)
    {
        cin >> b[i];
        c[b[i]]++;
    }

    int ans = 0;
    int cnt = 0;
    // 初始窗口
    for (int i = 0; i < m; i++)
    {
        if (c[a[i]] && d[a[i]] < c[a[i]])
        {
            ans++;
            d[a[i]]++;
        }
        else if (c[a[i]])
        {
            d[a[i]]++;
        }
    }
    if (ans >= k)
    {
        cnt++;
    }
    // 滑动窗口
    for (int i = m; i < n; i++)
    {
        // 前窗口部分
        if (c[a[i - m]] && d[a[i - m]] <= c[a[i - m]])
        {
            ans--;
            d[a[i - m]]--;
        }
        else if (c[a[i - m]])
        {
            d[a[i - m]]--;
        }
        // 后窗口部分
        if (c[a[i]] && d[a[i]] < c[a[i]])
        {
            ans++;
            d[a[i]]++;
        }
        else if (c[a[i]])
        {
            d[a[i]]++;
        }
        if (ans >= k)
        {
            cnt++;
        }
    }
    cout << cnt << endl;
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t)
    {
        solve();
        t--;
    }
    return 0;
}

思考：为什么 $c$ 和 $d$ 不用数组而用 map ？

如果用数组，为了避免前一次 solve( ) 函数会对下一次 solve( ) 产生的影响，我们每次都要对数组 $c$ ，$d$ 进行初始化，而 memset( ) 对这两个数组初始化，而 memset( ) 的时间复杂度是 $O(n)$ ，在这里算上 $t$ 的最大情况 $10^4$ 次，运算量来到 $10^{10}$ ，会超时。