1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 typedef long long ll; 6 struct Point{int v,p;}t[100001]; 7 bool operator < (const Point &a,const Point &b){return a.v<b.v;} 8 int sumv[350],ma[100001],en,a[100001],b[100001],tot[350],l[350],r[350],num[100001],sum=1,K,n,m; 9 ll ans=999999999999999999,tAns;10 void makeblock()11 {12     int sz=sqrt(en); if(!sz) sz=1;13     for(;sum*sz<en;++sum)14       {15           l[sum]=r[sum-1]+1; r[sum]=sum*sz;16           for(int i=l[sum];i<=r[sum];++i) num[i]=sum;17       }18     l[sum]=r[sum-1]+1; r[sum]=en;19     for(int i=l[sum];i<=r[sum];++i) num[i]=sum;20 }21 void Insert(const int &x){++b[x]; ++tot[num[x]]; sumv[num[x]]+=(ll)ma[x];}22 void Delete(const int &x){--b[x]; --tot[num[x]]; sumv[num[x]]-=(ll)ma[x];}23 int Query(const int &x)24 {25     int cnt=0; ll now=0;26     for(int i=1;;i++)27       {28         cnt+=tot[i]; now+=sumv[i];29         if(cnt>=x)30           {31               cnt-=tot[i]; now-=sumv[i];32             for(int j=l[i];;j++)33               {34                 cnt+=b[j]; now+=(ll)ma[j]*(ll)b[j];35                 if(cnt>=x)36                   {37                       cnt-=b[j]; now-=(ll)ma[j]*(ll)b[j];38                       tAns=((ll)ma[j]*(ll)cnt-now);39                       return j;40                   }41               }42           }43       }44 }45 void Next_Sum(const int &x)46 {47     int cnt=0; ll now=0;48     for(int i=x+1;i<=r[num[x]];++i) {cnt+=b[i]; now+=(ll)ma[i]*(ll)b[i];}49     for(int i=num[x]+1;i<=sum;++i) {cnt+=tot[i]; now+=sumv[i];}50     tAns+=(now-(ll)ma[x]*(ll)cnt);51 }52 int main()53 {54     scanf("%d%d",&n,&m); K=(m>>1)+1;55     for(int i=1;i<=n;++i)56       {57           scanf("%d",&t[i].v);58           t[i].p=i;59       } sort(t+1,t+n+1);60     ma[a[t[1].p]=++en]=t[1].v;61     for(int i=2;i<=n;++i)62       {63           if(t[i].v!=t[i-1].v) ++en;64           ma[a[t[i].p]=en]=t[i].v;65       } makeblock();66     for(int i=1;i<=m;++i) Insert(a[i]);67     int t=Query(K); Next_Sum(t); ans=min(ans,tAns);68     for(int i=m+1;i<=n;++i)69       {70           Delete(a[i-m]); Insert(a[i]);71           int t=Query(K);72         Next_Sum(t);73         ans=min(ans,tAns);74       } printf("%lld\n",ans);75     return 0;76 }