# HDU 6058 Kanade’s sum （技巧）

## 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]$ .

## 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


## AC 代码

#include<bits/stdc++.h>
using namespace std;

typedef __int64 LL;

const int maxn = 5e5+10;
int a[maxn];
int pre[maxn];
int nex[maxn];
int wei[maxn];
int stk1[85];
int stk2[85];
int top1,top2;

int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1; i<=n; i++)
{
scanf("%d",a+i);
wei[a[i]]=i;
pre[i]=i-1;
nex[i]=i+1;
}
pre[0]=-1,nex[n+1]=n+2;
LL ans=0;
for(int i=1; i<=n; i++)
{
int x=wei[i];
top1=top2=0;
for(int j=x; j>=0&&top1<=k; j=pre[j])
stk1[++top1]=j;
for(int j=x; j<=n+1&&top2<=k; j=nex[j])
stk2[++top2]=j;
for(int j=k-top2+2; j<=top1-1; j++)
ans+=LL(stk1[j]-stk1[j+1])*LL(stk2[k-j+2]-stk2[k-j+1])*i;
nex[pre[x]]=nex[x];
pre[nex[x]]=pre[x];
}
printf("%I64d\n",ans);
}
return 0;
}