[POI2008]砖块Klo

题目

爆炸(OJ)机子太慢了吧实在不想打平衡树了

做法

烂大街的一个概念：求中位数
然后求前缀差和后缀差，主席树模板题

注意(int)和(long long)

My complete code

#include<bits/stdc++.h>
#pragma GCC optimize (2)
#pragma G++ optimize (2)
using namespace std;
typedef long long LL;
inline LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<'0' || c>'9'){ if(c=='-')f=-1; c=getchar(); }
	while(c>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0', c=getchar();
	return x*f;
}
const int inf=0x3f3f3f3f,maxn=1e7+9;
int n,k,nod;
int size[maxn],son[maxn][2],a[maxn],root[maxn],b[maxn],id[maxn];
LL sum[maxn];
void Update(int &now,int pre,int l,int r,int x,int val){
	now=++nod;
	size[now]=size[pre]+1;
	sum[now]=sum[pre]+(LL)val;
	if(l==r) return;
	int mid(l+r>>1);
	if(x<=mid){
		Update(son[now][0],son[pre][0],l,mid,x,val);
		son[now][1]=son[pre][1];
	}else{
		Update(son[now][1],son[pre][1],mid+1,r,x,val);
		son[now][0]=son[pre][0];
	}
}
int Qkth(int now,int pre,int l,int r,int k){
	if(l==r) return b[l];
	int ret(size[son[now][0]]-size[son[pre][0]]);
	int mid(l+r>>1);
	if(k>ret) return Qkth(son[now][1],son[pre][1],mid+1,r,k-ret);
	else return Qkth(son[now][0],son[pre][0],l,mid,k);
}
LL Qll(int now,int pre,int l,int r,int x,int val){
	if(l==r) return (LL)val-b[l];
	int mid(l+r>>1);
	if(x<=mid) return Qll(son[now][0],son[pre][0],l,mid,x,val);
	else return (LL)(size[son[now][0]]-size[son[pre][0]])*val-(sum[son[now][0]]-sum[son[pre][0]])+Qll(son[now][1],son[pre][1],mid+1,r,x,val);
}
LL Qbg(int now,int pre,int l,int r,int x,int val){
	if(l==r) return b[l]-val;
	int mid(l+r>>1);
	if(x<=mid) return Qbg(son[now][0],son[pre][0],l,mid,x,val)+(sum[son[now][1]]-sum[son[pre][1]])-(LL)(size[son[now][1]]-size[son[pre][1]])*val;
	else return Qbg(son[now][1],son[pre][1],mid+1,r,x,val);
}
int main(){
	n=Read(); k=Read();
	for(int i=1;i<=n;++i)
		a[i]=b[i]=Read();
	sort(b+1,b+1+n);
	int cnt=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;++i){
		id[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
	    Update(root[i],root[i-1],1,cnt,id[i],a[i]);
	}
	int mid(k+1>>1),fir,mi;
	LL ans(1e18);
	for(int l=1;l+k-1<=n;++l){
		int r(l+k-1);
		LL ret(0);
		int zw=Qkth(root[r],root[l-1],1,cnt,mid);
		int x=lower_bound(b+1,b+1+cnt,zw)-b;
		ret+=Qll(root[r],root[l-1],1,cnt,x,zw);
		ret+=Qbg(root[r],root[l-1],1,cnt,x,zw);
		if(ret<ans){
			fir=l; mi=zw;
		    ans=ret;
	    }
	}
	printf("%lld
",ans);
	for(int i=fir;i<=fir+k-1;++i) a[i]=mi;
	for(int i=1;i<=n;++i) printf("%d
",a[i]);
	return 0;
}