Problem Description
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
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
5 2
1 2 3 4 5
Sample Output
30
题意：输入n,k 然后输入n个数（1~n的排列），求所有子区间的第k大数之和（长度小于k的区间值为0）。
思路：考虑每个数的贡献值，对于每个数求有多少个区间的第k大数是它，所以我们需要求出每个数向左比它大的k个数的位置，向右比它大的k个数的位置，根据这些位置就可以算出有多少区间它是第k大（这个就不详细说了），那么怎么求向左向右比它大的k数的位置呢，直接求复杂度比较高，我们可以按照1~n的数值大小顺序求向左向右的比它大的k个数的位置，用链表维护，算完i之后，将i从链表里面删除，那么剩余的都是比i+1大的数了，所以直接向左右遍历k个数即可。
代码如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=5e5+;
struct Node
{
int x;
int l,r;
}t[N];
int a[N], L[], R[]; int main()
{
int T,n,k; cin>>T;
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
scanf("%d",&t[i].x);
t[i].l=i-; t[i].r=i+;
a[t[i].x]=i;
}
t[].l=-; t[n].r=-; LL ans=;
for(int i=;i<=n;i++)
{
//ans=0;
int pos=a[i];
int tot=;///右
for(int j=t[pos].r;j!=-;j=t[j].r)
{
R[++tot]=j;
if(tot>=k) break;
}
R[]=tot;
if(tot<k) R[tot+]=n+; tot=; ///左
for(int j=t[pos].l;j!=-;j=t[j].l)
{
L[++tot]=j;
if(tot>=k) break;
}
L[]=tot;
if(tot<k) L[tot+]=; int l=t[pos].l;
int r=t[pos].r;
if(l>) t[l].r=r;
if(r>) t[r].l=l; for(int j=L[]; j>=; j--)
{
if(j>=k) continue;
int x=k--j;
if(x>R[]) continue;
int l=L[j]-L[j+];
if(j==) l=pos-L[];
int r=R[x+]-R[x];
if(x==) r=R[]-pos;
ans+=(LL)l*(LL)r*(LL)t[pos].x;
}
}
printf("%lld\n",ans);
}
return ;
}