题解 P3466 【[POI2008]KLO-Building blocks】
CodyTheWolf · · 题解
解法：FHQ_Treap
当然也不是裸的Treap QwQ
先行提醒：记得开longlong QwQ
根据题意，很想出步骤：
-
1.枚举一个长度为k的区间（从
[1,k] 到[n-k+1,n] ) -
2.计算中位数。
-
3.将中位数左边的数分别加到中位数，右边的数分别减到中位数
当然，这个不需要模拟，纯计算就好，设左边的元素有
l 个，右边有r 个,左边的元素为Al ，右边的元素为Ar （左右都不包括中位数）,中位数为m ，那么这个区间对应的答案就是：ans=(l*m-\sum Al)+(\sum Ar-r*m) 计算两边需要补上和丢掉的砖块，这个式子应该很好理解的
QwQ
解法很多：对顶堆，线段树和平衡树……
这里讲讲单棵平衡树怎么做
-
其实非常简单，只需要加入一个sum数组记录子树和就好，size更新的时候sum跟着更新，很简单：
sum[now]=sum[lson]+sum[rson]+val[now] ; -
每次固定平衡树有k个元素，也就是我们需要枚举的区间，移动区间时，我们在Treap上删掉最左的数，加入最右边+1（也就是待加入区间）的数。
-
中位数用求排名的方法很好做到，注意如果k为奇数偶数计算中位数的区别（小学知识，不知道就自己百度吧QwQ）
-
知道了中位数，我们把堆分成x,y,z三个堆，使（x堆所有元素）<mid，（y堆所有元素）==mid，（z堆所有元素）>mid，代码如下：
split(root,mid,x,z),split(x,mid-1,x,y); -
因为我们有sum和size数组，很容易能得到左右的元素个数分别是
size[x],size[z] ，左右元素和分别是sum[x],sum[z] 。查询完记得合并堆。再按照上面算ans的式子算一下，和最终答案取min就好。 -
计算完如果比最终答案小的话记得记录区间
[l,r] 和中位数m ，最后输出最后状态的时候直接把原数组输出，到[l,r] 的时候记得全部换成m 即可。
CODE
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
const long long maxn=2e5+5,INF=0x7fffffffffffff;
long long a[maxn];
long long n,k;
long long l,r;
long long ans_mid,ans_l,ans_r,ans=INF;
struct Fhq_Treap
{
long long l[maxn],r[maxn],sz[maxn],val[maxn],heap[maxn],sum[maxn];
long long num,root,x,y,z;
inline void update(long long pst)
{
sz[pst]=sz[l[pst]]+sz[r[pst]]+1;
sum[pst]=sum[l[pst]]+sum[r[pst]]+val[pst];
return;
}
inline long long new_node(long long key)
{
sz[++num]=1,sum[num]=val[num]=key,heap[num]=rand();
return num;
}
inline void split(long long pst,long long key,long long &x,long long &y)
{
if(!pst)
{
x=y=0;
return;
}
if(val[pst]<=key)
x=pst,split(r[pst],key,r[pst],y);
else
y=pst,split(l[pst],key,x,l[pst]);
update(pst);
return;
}
inline long long merge(long long x,long long y)
{
if(!x||!y)
return x+y;
if(heap[x]<heap[y])
{
r[x]=merge(r[x],y),update(x);
return x;
}
else
{
l[y]=merge(x,l[y]),update(y);
return y;
}
}
inline long long kth(long long pst,long long rak)
{
if(rak<=sz[l[pst]])
return kth(l[pst],rak);
if(rak==sz[l[pst]]+1)
return val[pst];
return kth(r[pst],rak-sz[l[pst]]-1);
}
inline void add(long long key)
{
split(root,key,x,y);
root=merge(x,merge(new_node(key),y));
return;
}
inline void del(long long key)
{
split(root,key,x,z),split(x,key-1,x,y);
y=merge(l[y],r[y]);
root=merge(x,merge(y,z));
return;
}
inline long long query(long long key)
{
split(root,key,x,z),split(x,key-1,x,y);
long long sz1=sz[x],sz2=sz[z];
long long ans1=sum[x],ans2=sum[z];
root=merge(x,merge(y,z));
long long l=sz1*key-ans1,r=ans2-sz2*key;
return l+r;
}
}FT;
signed main(void)
{
scanf("%lld %lld",&n,&k);
for(long long i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(long long i=0;i<k;i++)
FT.add(a[i]);
l=0,r=k-1;
for(long long i=k,mid;i<=n;i++)
{
l++,r++;
FT.del(a[l-1]),FT.add(a[r]);
if(k&1)
mid=FT.kth(FT.root,(k>>1)+1);
else
mid=(FT.kth(FT.root,k>>1)+FT.kth(FT.root,(k>>1)+1))>>1;
long long temp=FT.query(mid);
if(temp<ans)
ans=temp,ans_mid=mid,ans_l=l,ans_r=r;
}
printf("%lld\n",ans);
for(long long i=1;i<ans_l;i++)
printf("%lld\n",a[i]);
for(long long i=ans_l;i<=ans_r;i++)
printf("%lld\n",ans_mid);
for(long long i=ans_r+1;i<=n;i++)
printf("%lld\n",a[i]);
return 0;
}