C++14(g++5.4) 解法, 执行用时: 77ms, 内存消耗: 4460K, 提交时间: 2019-05-28 16:26:36

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<bits/stdc++.h>
#define N 400010
#define maxn 100000
#define lson k<<1
#define rson k<<1|1
using namespace std;
int sum[N],n,m,k,a[maxn+10];
long long prosum[N],ans;

 void add(int x,int d,int l=0,int r=maxn,int k=1)
{
    sum[k]+=d;
    prosum[k]+=x*d;
    if(l==r)
        return;
    int mid=l+r>>1;
    if(x<=mid)
        add(x,d,l,mid,lson);
    else
        add(x,d,mid+1,r,rson);
    return;
}
 void kth(int p,int l=0,int r=maxn,int k=1)
{
    if(l==r)
    {
        ans+=(long long)l*p;
        return;
    }
    int s=sum[lson],mid=l+r>>1;
    if(s>=p)
    {
        kth(p,l,mid,lson);
        return;
    }
    ans+=prosum[lson];
    kth(p-s,mid+1,r,rson);
    return;
}
int main()
{
    cin>>n>>m>>k;
    for(register int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        add(a[i],1);
        if(i>=m)
        {
            if(i>m)
            add(a[i-m],-1);
        kth(k);
        }
    }
    printf("%lld",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 40ms, 内存消耗: 1252K, 提交时间: 2020-03-16 21:37:21

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=100005;
typedef long long LL;
int n,m,K,Now,Num,a[MAXN],hsh[MAXN];
LL Ans,Sum;
int main()
{
	cin>>n>>m>>K;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<m;i++) hsh[a[i]]++;hsh[a[0]]++;Now=0,Num=hsh[a[0]];
	for(int i=m;i<=n;i++)
	{
		hsh[a[i-m]]--,hsh[a[i]]++;
		Num+=(a[i-m]>Now?0:-1)+(a[i]>Now?0:1);
		if(a[i-m]<=Now) Sum-=a[i-m];
		if(a[i]<=Now) Sum+=a[i];
		while(Num-hsh[Now]>K) Num-=hsh[Now],Sum-=(LL)hsh[Now]*Now,Now--;
		while(Num<K) Num+=hsh[++Now],Sum+=(LL)hsh[Now]*Now;
		Ans+=Sum-((LL)Num-K)*Now;
	}
	printf("%lld\n",Ans);
	return 0;
}