BZOJ1112[POI2008]砖块Klo——非旋转treap

题目描述

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

输入

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

输出

最小的动作次数

样例输入

5 3
3
9
2
3
1

样例输出

2

考虑对于只有$k$个数的序列的最优解，显然是将所有数都变成中位数(因为如果变成的数比中位数小或者大都会有多于一半的数要改变)。

那么我们只需要维护出有$k$个连续数的序列，求出中位数并维护比中位数大的数的和及比中位数小的数的和即可得到这$k$个数的最优解，用平衡树维护即可。

对于$n$个数的序列只需要每次对连续$k$个数维护信息并求最优解然后取最小值即可。每次将第$i$个数删除，再将第$i+k$个数插入。

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll ans;
int n,k;
int s[100010];
struct treap
{
	treap *ls,*rs;
	int size;
	int val;
	int rnd;
	ll sum;
	treap(){}
	treap(treap *son,int v)
	{
		ls=rs=son;
		size=1;
		val=v;
		sum=1ll*v;
		rnd=rand();
	}
	void pushup()
	{
		sum=ls->sum+rs->sum+val;
		size=ls->size+rs->size+1;
	}
}tr[100010],nil;
typedef treap* node;
node root,null,cnt;
node a,b,c;
inline void init()
{
	nil=treap(NULL,0);
	null=&nil;
	null->ls=null->rs=null;
	null->size=0;
	root=null;
	cnt=tr;
}
inline node build(int v)
{
	*cnt=treap(null,v);
	return cnt++;
}
inline node merge(node x,node y)
{
	if(x==null)
	{
		return y;
	}
	if(y==null)
	{
		return x;
	}
	if(x->rnd<y->rnd)
	{
		x->rs=merge(x->rs,y);
		x->pushup();
		return x;
	}
	else
	{
		y->ls=merge(x,y->ls);
		y->pushup();
		return y;
	}
}
inline void split1(node rt,node &x,node &y,int k)
{
	if(rt==null)
	{
		x=y=null;
		return ;
	}
	if(rt->ls->size>=k)
	{
		y=rt;
		split1(rt->ls,x,y->ls,k);
	}
	else
	{
		x=rt;
		split1(rt->rs,x->rs,y,k-1-rt->ls->size);
	}
	rt->pushup();
}
inline void split2(node rt,node &x,node &y,int k)
{
	if(rt==null)
	{
		x=y=null;
		return ;
	}
	if(rt->val>=k)
	{
		y=rt;
		split2(rt->ls,x,y->ls,k);
	}
	else
	{
		x=rt;
		split2(rt->rs,x->rs,y,k);
	}
	rt->pushup();
}
inline void query()
{
	split1(root,a,b,k/2);
	split1(b,b,c,1);
	ll res=1ll*a->size*b->val-a->sum;
	res+=c->sum-1ll*c->size*b->val;
	ans=min(res,ans);
	root=merge(merge(a,b),c);
}
int main()
{
	srand(12378);
	scanf("%d%d",&n,&k);
	ans=1ll<<60;
	init();
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&s[i]);
	}
	for(int i=1;i<=k;i++)
	{
		split2(root,a,b,s[i]);
		root=merge(merge(a,build(s[i])),b);
	}
	query();
	for(int i=k+1;i<=n;i++)
	{
		split2(root,a,b,s[i-k]);
		split1(b,b,c,1);
		root=merge(a,c);
		split2(root,a,b,s[i]);
		root=merge(merge(a,build(s[i])),b);
		query();
	}
	printf("%lld",ans);
}