2148E.md (2216B)
1 Source: https://codeforces.com/problemset/problem/2148/E 2 3 E. Split 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 Farmer John has an array $a$ containing $n$ positive integers and an integer $k$. 22 23 Let $a[l, r]$ be a subarray$^{\text{∗}}$ of $a$. He performs the following procedure to independently determine if subarray $a[l, r]$ is awesome: 24 25 * Initially, FJ has $k$ empty [multisets](https://en.wikipedia.org/wiki/Multiset), numbered from $1$ to $k$. 26 * Then, for each element $a_i$ ($1 \leq i \leq n$) in $a$: 27 + If $l\leq i\leq r$ (that is, $a_i$ is in the subarray $a[l, r]$), he places $a_i$ in multiset $1$, 28 + Otherwise, he places $a_i$ into any multiset he wants (which may be multiset $1$). 29 * Subarray $a[l, r]$ is awesome if there is some way for him to place elements such that, for every value $v$, all multisets contain the same number of elements with value $v$. In other words, he wants to make all multisets contain the exact same elements (ignoring ordering). 30 31 Output the number of awesome subarrays. 32 33 $^{\text{∗}}$For array $a$ of size $n$ and integers $1\leq l\leq r\leq n$, the subarray $a[l, r]$ denotes the array consisting of the elements $a_l, \ldots, a_r$, in order. 34 35 Input 36 37 The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. 38 39 The first line of each test case contains two integers $n$ and $k$ ($2 \leq k \le n \leq 2 \cdot 10^5$). 40 41 The following line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$). 42 43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each testcase, output one integer on a new line: the number of awesome subarrays. 48 49 Example 50 51 Input 52 53 ``` 54 4 55 56 3 2 57 58 1 1 1 59 60 4 2 61 62 1 2 1 2 63 64 8 2 65 66 3 3 3 3 2 2 2 2 67 68 6 3 69 70 1 1 1 1 1 1 71 ``` 72 73 Output 74 75 ``` 76 0 77 7 78 18 79 11 80 ``` 81 82 Note 83 84 Test case 1: $n=3$, $a=[1,1,1]$. 85 86 For $k=2$, you cannot finish with the same number of $1$'s in both multisets, so no subarray works. 87 88 Test case 2: $n=4$, $a=[1,2,1,2]$. 89 90 For $k=2$, the final state must give each multiset exactly one $1$ and one $2$. Thus a valid subarray can contain at most one $1$ and at most one $2$.