Responsive image

问题 C: Kanade's sum

问题 C: Kanade's sum

时间限制: 8 Sec  内存限制: 128 MB
提交: 25  解决: 14
[提交][状态][讨论版][命题人:]

题目描述

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

输入描述

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,output an integer, which means the answer.

样例输入

1

5 2

1 2 3 4 5

样例输出

30
[提交][状态]
ACM算法攻关部