关于堆求区间中位数问题

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//#pragma GCC optimize("Ofast")
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair((a),(b))
#define int ll

const int maxn=5e5+10;
const int inf=1e12;
const int mod=1e9+7;
int n,m,k,ans=inf,sum=0,l,tot;
int a[maxn];

struct heap {
	int sum;
	priority_queue<int> q1,q2;
	inline void push(int x) {
		q1.push(x);
		sum+=x;
	};
	inline void erase(int x) {
		q2.push(x);
		sum-=x;
	};
	inline void clean() {
		while(!q2.empty()&&q1.top()==q2.top()) {
			q1.pop();
			q2.pop();
		}
	};
	inline void pop() {
		while(!q2.empty()&&q1.top()==q2.top()) {
			q1.pop();
			q2.pop();
		}
		if(!q1.empty()) {
			sum-=q1.top();
			q1.pop();
		}
	};
	inline int top() {
		while(!q2.empty()&&q1.top()==q2.top()) {
			q1.pop();
			q2.pop();
		}
		return q1.top();
	};
	inline int size() {
		return q1.size()-q2.size();
	};
	inline bool empty() {
		return (size()==0);
	};
};

heap pq1,pq2;

inline void balance() {
	pq1.clean();
	pq2.clean();
	while(pq1.size()>pq2.size()+1) {
		pq1.sum-=pq1.top();
		pq2.sum+=pq1.top();
		pq2.push(-pq1.top());
		pq1.pop();
	}
	while(pq1.size()<pq2.size()) {
		pq1.sum+=pq2.top();
		pq2.sum-=pq2.top();
		pq1.push(-pq2.top());
		pq2.pop();
	}
}

inline int read() {
	int s=0,w=1;
	char ch=getchar();
	while(!isdigit(ch)) {
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
	return s*w;
}

inline void write(int x) {
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar('0'+x%10);
}

signed main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),k=read();
	for(int i=1; i<=n; ++i) a[i]=read();
	for(int i=1; i<=n; ++i) {
		if(!pq1.empty()&&a[i]>pq1.top()) {
			pq2.push(-a[i]);
			pq2.sum+=a[i];
		} else {
			pq1.push(a[i]);
			pq1.sum+=a[i];
		}
		balance();
		if(i>=k) {
			int mid=pq1.top();
			if(ans>abs(pq1.sum-pq2.sum-pq1.size()*mid+pq2.size()*mid)) {
				ans=abs(pq1.sum-pq2.sum-pq1.size()*mid+pq2.size()*mid);
				l=i-k+1;
				tot=mid;
			}
			if(pq1.top()>=a[i-k+1]) pq1.erase(a[i-k+1]);
			else pq2.erase(a[i-k+1]);
		}
	}
	write(ans),puts("");
	for(int i=1;i<=n;++i)
		if(i>=l&&i<=l+k-1) write(tot),puts("");
		else write(a[i]),puts("");
	return 0;
}

/*
5 3
3
9
2
3
1

out:
2
3
9
2
2
2

*/