priority_queue实现的对顶堆，细节超级多WA了十几次……但是理论上是最简便的orz其实是我已经不会写平衡树了
枚举左端点，显然要把这一段的高度搞成(l,l+k-1)的高度中位数，所以需要一个支持插入删除查询中位数的东西，我们使用对顶堆
然后关于删除，我们手动维护size和sum，删的时候直接减掉就行，然后堆里面放二元组高度和i，需要使用堆顶的时候，把i<l的pop掉就是可用堆顶了
注意q1最大值<=q2最小值，虽然判了但是还是会WA，在调整size的时候顺便判一下即可
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=100005;
int n,m,a[N],bl[N];
long long sm1,sm2,si1,si2,mn,ansl,ansm;
struct qwe
{
int v,id;
qwe(int V=0,int ID=0)
{
v=V,id=ID;
}
bool operator < (const qwe &b) const
{
return v<b.v;
}
};
struct ewq
{
int v,id;
ewq(int V=0,int ID=0)
{
v=V,id=ID;
}
bool operator < (const ewq &b) const
{
return v>b.v;
}
};
priority_queue<qwe>q1;
priority_queue<ewq>q2;
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
void del(int i)
{
while(!q1.empty()&&q1.top().id<i)
q1.pop();
while(!q2.empty()&&q2.top().id<i)
q2.pop();
}
void tiao(int i)
{
del(i);
while(!q1.empty()&&!q2.empty()&&q1.top().v>q2.top().v)
{
del(i);
si1--,si2++;
sm1-=q1.top().v,sm2+=q1.top().v;
q2.push(ewq(q1.top().v,q1.top().id)),q1.pop();
}
while(si1<si2)
{
del(i);
si1++,si2--;
sm1+=q2.top().v,sm2-=q2.top().v;
bl[q2.top().id]=1;
q1.push(qwe(q2.top().v,q2.top().id)),q2.pop();
}
while(si1-1>si2)
{
del(i);
si1--,si2++;
sm1-=q1.top().v,sm2+=q1.top().v;
bl[q1.top().id]=2;
q2.push(ewq(q1.top().v,q1.top().id)),q1.pop();
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=m;i++)
q1.push(qwe(a[i],i)),sm1+=a[i],si1++,bl[i]=1;
tiao(1);
ansl=1,ansm=q1.top().v,mn=ansm*si1-sm1+sm2-ansm*si2;//cerr<<endl;
//cerr<<q1.top().id<<" "<<q1.top().v<<" "<<sm1<<" "<<sm2<<" "<<si1<<" "<<si2<<endl;
for(int i=2;i+m-1<=n;i++)
{
if(bl[i-1]==1)
sm1-=a[i-1],si1--;
else
sm2-=a[i-1],si2--;
tiao(i);
del(i);
if(a[i+m-1]<=q1.top().v)
q1.push(qwe(a[i+m-1],i+m-1)),sm1+=a[i+m-1],si1++,bl[i+m-1]=1;
else
q2.push(ewq(a[i+m-1],i+m-1)),sm2+=a[i+m-1],si2++,bl[i+m-1]=2;
tiao(i);
del(i);
// cerr<<q1.top().id<<" "<<q1.top().v<<" "<<sm1<<" "<<sm2<<" "<<si1<<" "<<si2<<endl;
if(q1.top().v*si1-sm1+sm2-q1.top().v*si2<mn)
ansl=i,ansm=q1.top().v,mn=ansm*si1-sm1+sm2-ansm*si2;
}
printf("%lld
",mn);
// for(int i=1;i<=n;i++)
// {
// if(i>=ansl&&i<=ansl+m-1)
// printf("%lld
",ansm);
// else
// printf("%d
",a[i]);
// }
return 0;
}