显然我们需要考虑每一个区间，而这个问题显然我们都会做，这不就是这道题么，也就是说假如中位数是$mid$，区间和是$sum$，那么代价就是$\sum\limits_{i=l}^r |mid-num[i]|$
所以现在我们要维护这样的一个数据结构：支持删除/插入一个数，查询中位数和查询区间和
线段树？平衡树？写不来写不来，对顶堆即可解决
维护一个大根堆存区间中较小的一半数，小根堆存区间中较大的一半数，插入时比较一下两个堆的大小和堆顶元素(细节比较多，有一大坨讨论)。查询中位数就非常方便了，直接查询大根堆堆顶。查询区间和的操作也很好做，开两个变量记录一下就好了。唯一有点问题的是如何删除，因为std::priority_queue只能允许我们操作堆顶元素，解决方法一是手写堆，然而我不会，所以我用第二种方法：打标记。注意每次更新前后标记的下放，然后就做完了。
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=;
long long num[N],laz[M];
long long n,k,m,l,r,mid;
long long siz1,siz2,sum1,sum2,ans;
priority_queue<int> heap1;
priority_queue<int,vector<int>,greater<int> > heap2;
void Release()
{
while(!heap1.empty()&&laz[heap1.top()])
laz[heap1.top()]--,heap1.pop();
while(!heap2.empty()&&laz[heap2.top()])
laz[heap2.top()]--,heap2.pop();
}
void Push(long long x)
{
Release();
while(siz2&&siz1<m)
{
long long tpp=heap2.top();
heap2.pop(); heap1.push(tpp);
siz1++,siz2--,sum1+=tpp,sum2-=tpp;
Release();
}
if(!siz1)
heap1.push(x),siz1++,sum1+=x;
else
{
Release();
if(heap1.top()>x)
heap1.push(x),siz1++,sum1+=x;
else
heap2.push(x),siz2++,sum2+=x;
Release();
while(siz1>m)
{
long long tpp=heap1.top();
heap1.pop(); heap2.push(tpp);
siz1--,siz2++,sum1-=tpp,sum2+=tpp;
Release();
}
while(siz2&&siz1<m)
{
long long tpp=heap2.top();
heap2.pop(); heap1.push(tpp);
siz1++,siz2--,sum1+=tpp,sum2-=tpp;
Release();
}
}
}
void Pop(long long x)
{
laz[x]++;
if(heap1.top()>=x) siz1--,sum1-=x;
else siz2--,sum2-=x; Release();
}
long long cost()
{
return sum2-sum1+(k&)*heap1.top();
}
int main ()
{
scanf("%lld%lld",&n,&k),m=(k+)/;
for(int i=;i<=n;i++) scanf("%lld",&num[i]);
for(int i=;i<=k;i++) Push(num[i]);
ans=cost(),l=,r=k,mid=heap1.top();
for(int i=k+;i<=n;i++)
{
Pop(num[i-k]),Push(num[i]);
if(ans>cost()&&cost()>=)
ans=cost(),l=i-k+,r=i,mid=heap1.top();
}
printf("%lld\n",ans);
for(int i=;i<=n;i++)
(i>=l&&i<=r)?printf("%lld\n",mid):printf("%lld\n",num[i]);
return ;
}