$$D.不准确的后续搜索$$ $$每次测试的时间限制：2秒$$ $$每次测试的内存限制：256兆字节$$

---

题目描述

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$ ）–数组中元素的个数。( $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$ ) - 数组 $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$ 中良好子段的数量。

---

思路：使用<滑动窗口>动态统计当前枚举到的子区间里面各个元素的个数，从而动态统计匹配的数的个数cnt

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
const int N = 200010;int a[N],b[N];
map<int,int>ha,hb;void solve()
{ha.clear();hb.clear();int n,m,k; cin>>n>>m>>k;for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=m;i++)scanf("%d",&b[i]),hb[b[i]]++;int cnt=0,ans=0;for(int i=1;i<=n;i++){ha[a[i]]++;if(ha[a[i]]<=hb[a[i]])cnt++;if(i>m){ha[a[i-m]]--;if(ha[a[i-m]]<hb[a[i-m]])cnt--;}if(i>=m && cnt>=k)ans++;}cout<<ans<<endl;   
}int main()
{int t; cin>>t;while(t--){solve();}return 0;
}