Give you an array A[1..n]of length n.
Let f(l,r,k) be the k-th largest element of A[l..r].
Specially , f(l,r,k)=0 if r−l+1<k.
Give you k , you need to calculate ∑nl=1∑nr=lf(l,r,k)
There are T test cases.
1≤T≤10
k≤min(n,80)
A[1..n] is a permutation of [1..n]
∑n≤5∗105
1811: Kanade's sum
时间限制: 8 Sec 内存限制: 128 MB提交: 25 解决: 14
[提交][状态][讨论版][命题人:]
题目描述
输入描述
There is only one integer T on first line.
For each test case,there are only two integers n,k on first line,and the second line consists of n integers which means the array A[1..n]
For each test case,there are only two integers n,k on first line,and the second line consists of n integers which means the array A[1..n]
输出描述
For each test case,output an integer, which means the answer.
样例输入
1
5 2
1 2 3 4 5
样例输出
30来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版