这个问题是不是使用分治的办法解决?C语言怎么实现,具体的实现

Problem Description
After all the difficulties, Psyche and Cupid are finally getting married.

No ordinary pearls can hold Cupid's love for Psyche. So he has collected the Jewelry of Gods at the top of Mount Olympus to make her a chain.

There are n beads on the chain. The i-th bead is of the type Ai.

Being pretty in appearance and generous in her heart, Psyche decides to give one consecutive part of the chain to her mother.

To meet her mother's particular taste, that part must have at least one type of bead that appears x times exactly.

Psyche wants to know the number of ways to choose a part of the chain for her mother.

Note that two parts [L1,R1] and [L2,R2] are different only if L1≠L2 or R1≠R2.

Input
The first line of the input contains an integer T (1≤T≤15), which denotes the number of test cases.

For each test case, the first line contains two integers n,x (1≤n≤105,1≤x≤n).

The second line contains n integers, the i-th integer denotes Ai (0≤Ai≤109).

Output
For each test case, print an integer which denotes the number of parts Psyche can choose.

Sample Input
2
3 1
1 2 1
4 2
2 3 2 2

Sample Output
6
3

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!