Kanade’s sum
time limit per test 2 second memory limit per test 256 megabytes
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≤5e5

传送门:HDU6058

Input

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]

Output

For each test case,output an integer, which means the answer.

Sample Input

1
2
3
1
5 2
1 2 3 4 5

Sample Output

1
30

题解

题意:求所有区间第k大的数的和 思路很巧妙 枚举每一个x作为一个区间中的第k大,那么如果他前面有i个比他大的,后面一定有k-1-i比他大的 i的范围是0~(k-1) 然后注意到k的范围<=80 维护一个链表 从小到大枚举x 因为是从小到大枚举的(且枚举完会删除)所以链表中其他的元素都是严格大于x的 只要左遍历k次 右遍历k次 然后循环计算一下方案数 最后把x删去保证链表的单调性 举个例子:一开始是这样的 6 - 4 - 2 - 1 - 5 - 3 枚举1 后删去 6 - 4 - 2 - 5 - 3 枚举2 后删去 6 - 4 - 5 - 3 这样在枚举每一个x时(从小到大)最多只要左右各扫k次就可以了 计算需要在循环一遍k(相当于枚举左边有多少个比他大的) 总复杂度O(nk)
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.*;  
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int t=sc.nextInt();
while(sc.hasNext()){
int n=sc.nextInt();
int k=sc.nextInt();
int[]index=new int[n+2];
int[]pre=new int[n+2]; //自己实现一个链表
int[]next=new int[n+2];
for(int i=1;i<=n;i++){
int shu=sc.nextInt();
index[shu]=i; //记录一下在链表中的位置 方便下面枚举
pre[i]=i-1;
next[i]=i+1;
}
long res=0;
for(int i=1;i<=n-k+1;i++){ //从小到大枚举
int pos=index[i];
int a=pre[pos];
int b=next[pos];
//pw.println(pos+" "+a+" "+b);
int cnt=0;
ArrayList<Integer>list1=new ArrayList<Integer>();
ArrayList<Integer>list2=new ArrayList<Integer>();
list1.add(pos);
list2.add(pos);
while(a>0&&cnt<=k){
cnt++;
list1.add(a);
a=pre[a];
}
while(list1.size()<=k)list1.add(a);
cnt=0;
while(b<n+1&&cnt<=k){
cnt++;
list2.add(b);
b=next[b];
}
while(list2.size()<=k)list2.add(b);
for(int j=0;j<=k-1;j++){ //枚举左边有多少个比x大的 计算左右两边的有效区间 相乘即为对应的方案数
res+=(list1.get(j)-list1.get(j+1))*(long)(list2.get(k-1-j+1)-list2.get(k-1-j))*i;
}
next[pre[pos]]=next[pos]; //删去枚举的那个x
pre[next[pos]]=pre[pos];
}
pw.println(res);
pw.flush();
}

}
}