2149E.md (2337B)
1 Source: https://codeforces.com/problemset/problem/2149/E 2 3 E. Hidden Knowledge of the Ancients 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 In the world of Deepwoken, there exists an ancient artifact — Tablet of Infinite Knowledge, on which a sequence of $n$ mysterious symbols (each symbol is an integer) is engraved. 22 23 It is said that the true power of the artifact can only be revealed by finding all sacred fragments — continuous segments of the tablet that contain exactly $k$ distinct numbers, and their length must be between $l$ and $r$ (inclusive). 24 25 Formally: Given a sequence $a$ of length $n$ and integers $k$, $l$, $r$. You need to find the number of such boundaries $b$ and $c$ such that: 26 27 * $1 \le b \le c \le n$; 28 * among the elements [$a_{b}, a_{b + 1}, \dots, a_{c}$] there are exactly $k$ distinct numbers; 29 * $l \leq c - b + 1 \leq r$. 30 31 Input 32 33 Each test consists of several test cases. 34 35 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 36 37 The following describes the test cases. 38 39 The first line of each test case contains four integers: $n$, $k$, $l$, and $r$ $( 1 \le k \le n \le 2 \cdot 10^5, 1 \le l \le r \le n)$. 40 41 The second line contains $n$ numbers $a_i$ $(1 \le a_i \le 10^9)$ — the mysterious symbols. 42 43 It is guaranteed that the total value of $n$ over all test cases does not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each test, output a single integer on a separate line — the number of continuous subarrays that meet the specified conditions. 48 49 Example 50 51 Input 52 53 ``` 54 5 55 56 1 1 1 1 57 58 5 59 60 5 2 2 3 61 62 1 2 1 3 2 63 64 6 3 1 6 65 66 1 2 3 1 2 3 67 68 4 1 1 2 69 70 7 7 7 7 71 72 7 3 2 4 73 74 1 2 1 2 3 2 1 75 ``` 76 77 Output 78 79 ``` 80 1 81 82 5 83 84 10 85 86 7 87 88 5 89 ``` 90 91 Note 92 93 In the first test case $a=[5]$, there is only one subarray $[5]$, which has a length of 1 and contains exactly $1$ distinct number. 94 95 In the fourth test case $a=[7,7,7,7]$, any subarray of identical numbers gives exactly $1$ distinct number. The start and end of possible subarrays are: 96 97 * Length $1$: $[1,1]$, $[2,2]$, $[3,3]$, $[4,4]$. 98 * Length $2$: $[1,2]$, $[2,3]$, $[3,4]$. 99 100 In total: $7$. 101 102 In the fifth test case $a=[1,2,1,2,3,2,1]$: 103 104 * Length $2$: all subarrays have only $2$ distinct numbers. 105 * Length $3$: $[3,5]$, $[5,7]$. 106 * Length $4$: $[2,5]$, $[3,6]$, $[4,7]$. 107 108 In total: $5$.