链接:https://ac.nowcoder.com/acm/contest/900/B
来源:牛客网
空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format: %lld
题目描述
今天,YPC正在热舞之中,嘴里唱着BJLY的神曲,沉浸在了自己的世界里。 然而Taeyeon又突然抽了一下,问YPC一个问题: 在一个长度为n的区间中,子区间[1,m],[2,m+1],[3,m+2],...,[n-m+1,n]中每个区间前K小之和的和是多少。其中一个区间的前k小之和指的是将这个区间内的所有数从小到大排序后求出最前面的k个数之和
由于YPC热舞的起劲,无法自拔,于是这个问题只能你来回答。
输入描述:
第一行三个整数:n,m,K,意思如题 第二行n个正整数:a[i],意思如题
输出描述:
输出仅一行,每个区间前K小的数之和的和。示例1
输入
复制6 3 2 2 3 1 4 5 6
输出
复制21
说明
对于30%数据:1≤n,m≤1000,0≤k≤m≤n,0≤a[i]≤105,m接近于n/2 对于100%数据:1≤n,m≤105,0≤k≤m≤n,0≤a[i]≤105,m接近于n/2。保证数据纯随机示例2
输入
复制6 3 2 2 2 2 2 2 2
输出
复制16
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; int n,m,k; int c[maxn]; ll cnt[maxn<<2],sum[maxn<<2]; inline void update(int l,int r,int rt,int val,int w){ if(l==r){ cnt[rt]+=w; sum[rt]+=l*w; return; } int mid=l+r>>1; if(val<=mid){ update(l,mid,rt<<1,val,w); } else{ update(mid+1,r,rt<<1|1,val,w); } cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1]; sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } inline ll query(int l,int r,int rt,int k){ if(l==r){ return (ll)l*k; } int mid=l+r>>1; ll cur=cnt[rt<<1]; if(cur>=k){ return query(l,mid,rt<<1,k); } else{ return sum[rt<<1]+query(mid+1,r,rt<<1|1,k-cnt[rt<<1]); } } int main() { //freopen("1.txt","r",stdin); scanf("%d%d%d",&n,&m,&k); for(register int i=1;i<=n;++i){ scanf("%d",c+i); } for(register int i=1;i<=m;++i){ update(0,maxn-2,1,c[i],1); } ll ans=query(0,maxn-2,1,k); for(register int i=m+1;i<=n;++i){ update(0,maxn-2,1,c[i-m],-1); update(0,maxn-2,1,c[i],1); ans+=query(0,maxn-2,1,k); } printf("%lld\n",ans); return 0; }