CF2148E Split

Farmer John has an array $ a $ containing $ n $ positive integers and an integer $ k $ . 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: - Initially, FJ has $ k $ empty [multisets](https://en.wikipedia.org/wiki/Multiset), numbered from $ 1 $ to $ k $ . - Then, for each element $ a_i $ ( $ 1 \leq i \leq n $ ) in $ a $ : - If $ l\leq i\leq r $ (that is, $ a_i $ is in the subarray $ a[l, r] $ ), he places $ a_i $ in multiset $ 1 $ , - Otherwise, he places $ a_i $ into any multiset he wants (which may be multiset $ 1 $ ). - 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). Output the number of awesome subarrays. $ ^{\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.

The first line contains an integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The first line of each test case contains two integers $ n $ and $ k $ ( $ 2 \leq k \le n \leq 2 \cdot 10^5 $ ). The following line contains $ n $ space-separated integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each testcase, output one integer on a new line: the number of awesome subarrays.

Test case 1: $ n=3 $ , $ a=[1,1,1] $ . For $ k=2 $ , you cannot finish with the same number of $ 1 $ 's in both multisets, so no subarray works. Test case 2: $ n=4 $ , $ a=[1,2,1,2] $ . 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 $ .