only need your direction
(i got time limit exceed cause of generation of all subarray is okay but repeatedly sorting them for finding kth index is leads to tle. your direction will appreciable.Thank you)
You are given an array A1,A2,…,AN and an integer K. For each subarray S=[Al,Al+1,…,Ar] (1≤l≤r≤N):
Let's define an array B as S concatenated with itself m times, where m is the smallest integer such that m(r−l+1)≥K.
Next, let's sort B and define X=BK, i.e. as a K-th smallest element of B. Note that |B|≥K.
Then, let's define F as the number of occurrences of X in S.
The subarray S is beautiful if F occurs in S at least once.
Find the number of beautiful subarrays of A. Two subarrays Al,Al+1,…,Ar and Ap,Ap+1,…,Aq are different if l≠p or r≠q.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and K.
The second line contains N space-separated integers A1,A2,…,AN.
Output
For each test case, print a single line containing one integer - the number of beautiful subarrays.
Constraints
1≤T≤5
1≤N≤2,000
1≤K≤109
1≤Ai≤2000 for each valid i
Subtasks
Subtask #1 (20 points): 1≤N≤200
Subtask #2 (80 points): original constraints
Example Input
1
3 3
1 2 3
Example Output
3
Explanation
Example case 1: There are six subarrays of A: [1], [2], [3], [1,2], [2,3], [1,2,3]. The corresponding arrays B are [1,1,1], [2,2,2], [3,3,3], [1,2,1,2], [2,3,2,3], [1,2,3].
Three of the subarrays are beautiful: [1], [1,2] and [1,2,3]. For these subarrays, X is 1, 2 and 3 respectively (for example, for S=[1,2], B=[1,2,1,2] is sorted to [1,1,2,2] and X=2 is the 3-rd element). Then, F=1 for each of these subarrays, and each of these subarrays contains 1.
You are given an array A1,A2,…,AN and an integer K. For each subarray S=[Al,Al+1,…,Ar] (1≤l≤r≤N):
Let's define an array B as S concatenated with itself m times, where m is the smallest integer such that m(r−l+1)≥K.
Next, let's sort B and define X=BK, i.e. as a K-th smallest element of B. Note that |B|≥K.
Then, let's define F as the number of occurrences of X in S.
The subarray S is beautiful if F occurs in S at least once.
Find the number of beautiful subarrays of A. Two subarrays Al,Al+1,…,Ar and Ap,Ap+1,…,Aq are different if l≠p or r≠q.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and K.
The second line contains N space-separated integers A1,A2,…,AN.
Output
For each test case, print a single line containing one integer - the number of beautiful subarrays.
Constraints
1≤T≤5
1≤N≤2,000
1≤K≤109
1≤Ai≤2000 for each valid i
Subtasks
Subtask #1 (20 points): 1≤N≤200
Subtask #2 (80 points): original constraints
Example Input
1
3 3
1 2 3
Example Output
3
Explanation
Example case 1: There are six subarrays of A: [1], [2], [3], [1,2], [2,3], [1,2,3]. The corresponding arrays B are [1,1,1], [2,2,2], [3,3,3], [1,2,1,2], [2,3,2,3], [1,2,3].
Three of the subarrays are beautiful: [1], [1,2] and [1,2,3]. For these subarrays, X is 1, 2 and 3 respectively (for example, for S=[1,2], B=[1,2,1,2] is sorted to [1,1,2,2] and X=2 is the 3-rd element). Then, F=1 for each of these subarrays, and each of these subarrays contains 1.
Last edited on
Topic archived. No new replies allowed.