Rt，思路就是维护区间中位数，SPJ显示是步数输出得不对，splay 板子应该是问题不大。

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;

int rt,tot;
struct node
{
	int fa,son[2],sz,cnt,v,sum;	
}t[N];
void clear(int u)
{
	t[u].fa = t[u].son[0] = t[u].son[1] = t[u].v = t[u].sz = t[u].cnt = t[u].sum = 0;
}
bool get(int u)
{
	return t[t[u].fa].son[1] == u;
}
void upd(int u)
{
	t[u].sz = t[t[u].son[0]].sz + t[t[u].son[1]].sz + t[u].cnt;
	t[u].sum = t[t[u].son[0]].sum + t[t[u].son[1]].sum + t[u].cnt*t[u].v;
}
void rot(int u)
{
	int k = get(u),v = t[u].fa,w = t[v].fa;
	t[v].son[k] = t[u].son[k^1];
	if(t[u].son[k^1])t[t[u].son[k^1]].fa = v;
	t[u].son[k^1] = v;
	t[v].fa = u,t[u].fa = w;
	if(w)t[w].son[t[w].son[1] == v] = u;
	upd(v),upd(u);
}
void splay(int u)
{
	for(int v = t[u].fa;v = t[u].fa,v;rot(u))
		if(t[v].fa)rot(get(u) == get(v)?v:u);
	rt = u;
}
int build(int x)
{
	++tot;
	t[tot].v = t[tot].sum = x;
	t[tot].cnt = t[tot].sz = 1;
	return tot;
}
void ins(int las,int u,int x)
{
	if(!u)
	{
		u = build(x);
		if(!rt)rt = u;
		t[u].fa = las;
		if(las)t[las].son[x > t[las].v] = u,upd(las);
		splay(u);
		return;
	}
	if(x == t[u].v)
	{
		t[u].cnt++;
		upd(u);
		splay(u);
		return;
	}
	ins(u,t[u].son[x > t[u].v],x);
}
int rk(int u,int x)
{
	if(!u)return 1;
	if(x < t[u].v)return rk(t[u].son[0],x);
	if(x == t[u].v)
	{
		int ret = t[t[u].son[0]].sz + 1;
		splay(u);
		return ret;
	}
	if(x > t[u].v)return t[t[u].son[0]].sz + t[u].cnt + rk(t[u].son[1],x);
}
int th(int u,int x)
{
	if(!u)return 0;
	if(x <= t[t[u].son[0]].sz)return th(t[u].son[0],x);
	x -= t[t[u].son[0]].sz + t[u].cnt;
	if(x <= 0)
	{
		splay(u);
		return t[u].v;
	}
	return th(t[u].son[1],x);
}
int pre()
{
	int u = t[rt].son[0];
	if(!u)return 0;
	while(t[u].son[1])u = t[u].son[1];
	splay(u);
	return u;
}
int nxt()
{
	int u = t[rt].son[1];
	if(!u)return 0;
	while(t[u].son[0])u = t[u].son[0];
	splay(u);
	return u;
}
void del(int x)
{
	rk(rt,x);
	int u = rt;
	if(t[u].cnt > 1)
	{
		t[u].cnt--;
		upd(u);
		return;
	}
	if(!t[u].son[0] && !t[u].son[1])
	{
		clear(u);
		rt = 0;
		return;
	}
	if(t[u].son[0] && !t[u].son[1])
	{
		rt = t[u].son[0];
		t[rt].fa = 0;
		clear(u);
		return;
	}
	if(!t[u].son[0] && t[u].son[1])
	{
		rt = t[u].son[1];
		t[rt].fa = 0;
		clear(u);
		return;
	}
	rt = pre();
	t[rt].fa = 0;
	t[rt].son[1] = t[u].son[1];
	upd(rt);
	clear(u);
}

int n,k,h[N];
int ans,num = 1e18,id;

signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i = 1;i <= n;i++)
	{
		scanf("%lld",&h[i]);
		ins(0,rt,h[i]);
		if(i > k)del(h[i-k]);
		if(i >= k)
		{
			th(rt,k+1>>1);
			int l = t[rt].son[0],r = t[rt].son[1],now = t[rt].v;
			int x = now*t[l].sz-t[l].sum + t[r].sum-now*t[r].sz;
			if(x < num)
			{
				num = x;
				ans = now;
				id = i-k+1;
			}
		}
	}
	printf("%lld\n",num);
	for(int i = 1;i <= n;i++)
	{
		if(i >= id && i <= id+k-1)printf("%lld\n",ans);
		else printf("%lld\n",h[i]);
	}
	return 0;
}