HDU-Kanade's sum-模拟-CSDN博客

本文链接：https://blog.csdn.net/chenyang890/article/details/77248524

本篇博客介绍了一道算法题目，该题目要求计算一个整数数组所有子数组中第K大元素的总和。通过巧妙地将复杂问题分解为一系列较小的问题，文章详细解释了如何找到每个数作为第K大元素出现的所有子数组，并给出了完整的C++实现代码。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Kanade's sum

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2799 Accepted Submission(s): 1155

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

Sample Output

解题思路

题意：算出数组[n]的所以子数组的第k大的总和

将大问题化成n的小问题，找到当前数被看做第k大的数的所有子数组（可以看成找到比当前位置之前大的k个数和当前位置之后的k个数，记录每个数的位置，可以找到中间比当前数小的个数）

解题代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    int n,k;
    int a[5*100001];
    int aa[5*100001];
    long long int ans;
    while(T--)
    {
        memset(a,0x3f3f3f,sizeof(a));
        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++)
        {
            int right=0;
            int left=0;
            for(int j=i+1;j<=n+1;j++)
            {
               if(a[j]>a[i])//在i位置后面比当前数大的
               {
                   right++;
                   aa[k+right]=j;
               }
               if(right==k)
               break;
            }
            for(int j=i-1;j>=0;j--)
            {
                if(a[j]>a[i])//在i位置前面比当前数大的
                {
                    left++;
                    aa[k-left]=j;
                }
                if(left==k)
                    break;
            }
            aa[k]=i;
            int lnum,rnum;
            for(int j=k+right-1;j>=k;j--)
            {
                if(j-k+1<k-left+1)
                    break;
                lnum=aa[j-k+1]-aa[j-k];
                rnum=aa[j+1]-aa[j];
                ans+=(long long int)(lnum*rnum)*a[i];
            }

        }
        printf("%lld\n",ans);
    }

    return 0;
}