1955D.md (2408B)
1 Source: https://codeforces.com/problemset/problem/1955/D 2 3 D. Inaccurate Subsequence Search 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Maxim has an array $a$ of $n$ integers and an array $b$ of $m$ integers ($m \le n$). 22 23 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$. 24 25 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. 26 27 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. 28 29 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. 30 31 Input 32 33 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 34 35 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. 36 37 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. 38 39 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. 40 41 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$. 42 43 Output 44 45 For each test case, output the number of good subsegments of array $a$ on a separate line. 46 47 Example 48 49 Input 50 51 ``` 52 5 53 54 7 4 2 55 56 4 1 2 3 4 5 6 57 58 1 2 3 4 59 60 7 4 3 61 62 4 1 2 3 4 5 6 63 64 1 2 3 4 65 66 7 4 4 67 68 4 1 2 3 4 5 6 69 70 1 2 3 4 71 72 11 5 3 73 74 9 9 2 2 10 9 7 6 3 6 3 75 76 6 9 7 8 10 77 78 4 1 1 79 80 4 1 5 6 81 82 6 83 ``` 84 85 Output 86 87 ``` 88 4 89 3 90 2 91 4 92 1 93 ``` 94 95 Note 96 97 In the first example, all subsegments are good. 98 99 In the second example, good subsegments start at positions $1$, $2$, and $3$. 100 101 In the third example, good subsegments start at positions $1$ and $2$.