codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.