Kanade's sum
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2496 Accepted Submission(s): 1037
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
Source
2017 Multi-University Training Contest - Team 3
Recommend
liuyiding
题意：给出一个序列，问这个序列中所有区间第k大的为多少
解题思路：用链表来处理， 每次找到链表中最小的数字，那么其他数字必然都是比它大的，处理出它前面的k个数字和后面的k个数字，那么前后延伸的长度就是对该点的贡献，然后求一下乘积的和即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;
const LL mod=1000000007;
int n,k,x[500010],a[100],b[100];;
int pos[500010],pre[500010],nt[500010];
LL ans;
void change(int x)
{
pre[nt[x]]=pre[x];
nt[pre[x]]=nt[x];
}
LL solve(int x)
{
int sum1=0,sum2=0;
for(int i=x; i; i=pre[i])
{
a[++sum1]=i-pre[i];
if(sum1==k) break;
}
for(int i=x; i<=n; i=nt[i])
{
b[++sum2]=nt[i]-i;
if(sum2==k) break;
}
LL sum=0;
for(int i=1; i<=sum1; i++)
if(k-i+1<=sum2) sum+=1LL*a[i]*b[k-i+1];
return sum;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
for(int i=1; i<=n; i++)scanf("%d",&a[i]),pos[a[i]]=i;
for(int i=0; i<=n+1; i++) pre[i]=i-1,nt[i]=i+1;
pre[0]=0;
nt[n+1]=n+1;
ans=0;
for(int i=1; i<=n; i++)
{
int x=pos[i];
ans+=solve(x)*i;
change(x);
}
printf("%lld\n",ans);
}
return 0;
}
