hdu 6058 Kanade's sum 枚举

本文主要是介绍hdu 6058 Kanade's sum 枚举，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

枚举左和右有多少个比他大的就好了，注意超出边界的时候边界是可以取的，不超出边界的时候那个数是不能取的
比如 1 2 4 5 3 的时候 k=2时，4右边有一个比他大的，所以最右边是可以取到3，但是1 2 3 5 4 时，4就不能被取到

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=5e5+5;
int l[maxn],r[maxn],cntl,cntr,a[maxn];
int main()
{int t;scanf("%d",&t);while(t--){int n,k;ll ans=0;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){cntl=cntr=1;int j;for(j=i+1;j<=n;j++){if(cntr>k)break;if(a[j]>a[i])r[cntr++]=j-i;}if(j>n)r[cntr]=n-i+1;for(j=i-1;j>=1;j--){if(cntl>k)break;if(a[j]>a[i])l[cntl++]=i-j;}if(j<=1)l[cntl]=i;for(j=0;j<cntl;j++){if(k-j-1>=cntr)continue;ll _n=l[j+1]-l[j];ll _m=r[k-j]-r[k-j-1];ans+=(ll)_n*_m*a[i];}}printf("%lld\n",ans);}return 0;
}

这篇关于hdu 6058 Kanade's sum 枚举的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---