1112: [POI2008]砖块Klo

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2910 Solved: 1026
[Submit][Status][Discuss]

Description
N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.

Input
第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000

Output
最小的动作次数

Sample Input
5 3

3

9

2

3

1
Sample Output
2

不难想到，对于一个区间，我们要找到把不同数字变为相同的最小步数，就是要找到中位数，所以我们就要去维护中位数。
诶？中位数不就是第k大的问题吗？于是我们可以用权值线段树去维护。

然后权值线段树维护区间个数，和权值和即可。

这道题用平衡树会快很多，权值线段树不离散化会TLE（或者我写得菜）。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,k,m,a[N],res=1e18,vis[N*10],b[N],cnt;
struct node{
	int l,r,sum,num;
}t[N<<2];
inline void push_up(int p){
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
	t[p].num=t[p<<1].num+t[p<<1|1].num;
}
void build(int p,int l,int r){
	t[p].l=l; t[p].r=r;
	if(l==r)	return ; int mid=l+r>>1;
	build(p<<1,l,mid); build(p<<1|1,mid+1,r);
}
void change(int p,int x,int v){
	if(t[p].l==t[p].r){
		t[p].sum+=b[x]*v,t[p].num+=v;	return ;
	}
	int mid=t[p].l+t[p].r>>1;	
	if(x<=mid)	change(p<<1,x,v);
	else	change(p<<1|1,x,v);
	push_up(p);
}
int ask(int p,int l,int r,bool flag){
	if(t[p].l==l&&t[p].r==r)	return (flag?t[p].num:t[p].sum);
	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return ask(p<<1,l,r,flag);
	else if(l>mid)	return ask(p<<1|1,l,r,flag);
	else	return ask(p<<1,l,mid,flag)+ask(p<<1|1,mid+1,r,flag);
}
int kth(int p,int k){
	if(t[p].l==t[p].r)	return t[p].l;
	int mid=t[p].l+t[p].r>>1;	int ls=t[p<<1].num;
	if(k<=ls)	return kth(p<<1,k);
	else	return kth(p<<1|1,k-ls);
}
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)	scanf("%lld",&a[i]),b[i]=a[i];
	sort(b+1,b+1+n); m=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=m;i++)	vis[b[i]]=++cnt;
	build(1,1,m);
	for(int i=1;i<=k;i++)	change(1,vis[a[i]],1);
	for(int i=k;i<=n;i++){
		int mid=kth(1,(k+1)/2),ln=0,rn=0,ls=0,rs=0;
		if(1<=mid-1)	ln=ask(1,1,mid-1,1);
		if(mid+1<=m)	rn=ask(1,mid+1,m,1);
		if(1<=mid-1) 	ls=ask(1,1,mid-1,0);
		if(mid+1<=m)	rs=ask(1,mid+1,m,0);
		res=min(res,rs-rn*b[mid]+ln*b[mid]-ls);
		change(1,vis[a[i-k+1]],-1); change(1,vis[a[i+1]],1);
	}
	printf("%lld\n",res);
	return 0;
}