Inaccurate Subsequence Search
Contest: Codeforces Round 938 (Div. 3)
Difficulty rating: 1400
Tags: data structures, two pointers

Maxim has an array $$$a$$$ of $$$n$$$ integers and an array $$$b$$$ of $$$m$$$ integers ($$$m \le n$$$).

Maxim considers an array $$$c$$$ of length $$$m$$$ to be good if the elements of array $$$c$$$ can be rearranged in such a way that at least $$$k$$$ of them match the elements of array $$$b$$$.

For example, if $$$b = [1, 2, 3, 4]$$$ and $$$k = 3$$$, then the arrays $$$[4, 1, 2, 3]$$$ and $$$[2, 3, 4, 5]$$$ are good (they can be reordered as follows: $$$[1, 2, 3, 4]$$$ and $$$[5, 2, 3, 4]$$$), while the arrays $$$[3, 4, 5, 6]$$$ and $$$[3, 4, 3, 4]$$$ are not good.

Maxim wants to choose every subsegment of array $$$a$$$ of length $$$m$$$ as the elements of array $$$c$$$. Help Maxim count how many selected arrays will be good.

In other words, find the number of positions $$$1 \le l \le n - m + 1$$$ such that the elements $$$a_l, a_{l+1}, \dots, a_{l + m - 1}$$$ form a good array.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le k \le m \le n \le 2 \cdot 10^5$$$) — the number of elements in arrays $$$a$$$ and $$$b$$$, the required number of matching elements.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of array $$$a$$$. Elements of the array $$$a$$$ are not necessarily unique.

The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^6$$$) — the elements of array $$$b$$$. Elements of the array $$$b$$$ are not necessarily unique.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. Similarly, it is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output the number of good subsegments of array $$$a$$$ on a separate line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, all subsegments are good.

In the second example, good subsegments start at positions $$$1$$$, $$$2$$$, and $$$3$$$.

In the third example, good subsegments start at positions $$$1$$$ and $$$2$$$.

Example input:
5
7 4 2
4 1 2 3 4 5 6
1 2 3 4
7 4 3
4 1 2 3 4 5 6
1 2 3 4
7 4 4
4 1 2 3 4 5 6
1 2 3 4
11 5 3
9 9 2 2 10 9 7 6 3 6 3
6 9 7 8 10
4 1 1
4 1 5 6
6

Example output:
4
3
2
4
1

Editorial:
How to check if two arrays are good? For each element of $$$b$$$, try to pair it with an element from array $$$a$$$. If we managed to create $$$k$$$ or more pairs, then the arrays are good.
Since rearranging the elements of the array is allowed, we will maintain three multisets $$$C$$$, $$$D$$$, and $$$E$$$. In $$$D$$$, we will store all elements from $$$b$$$ for which we found a pair, and in $$$C$$$ and $$$E$$$, all elements from $$$b$$$ and $$$a$$$ for which a pair was not found, i.e., $$$C \cap E = \emptyset$$$. Then the arrays are good if $$$|D| \ge k$$$.
It remains to understand how to find all good subsegments using this data organization. Suppose we shift the left boundary $$$l$$$ by $$$1$$$, simultaneously moving the right boundary, where $$$r = l + m - 1$$$. We need to remove the pair with the element $$$a_l$$$ from $$$D$$$, if it exists, and immediately try to find a replacement for the removed pair in $$$E$$$. After that, we try to find a pair for $$$a_r$$$ from $$$C$$$, and if a pair cannot be found, we place the element in $$$E$$$.
The complexity of the solution is $$$O(n \log n)$$$ or $$$O(n)$$$ if a hash table is used.