题目描述
N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.你还要求输出结束状态时,每柱砖的高度
（删除方案是SPJ）
1≤k≤n≤100 000
0≤hi≤1 000 000
题解
有连续K柱，必须知道是哪K柱比较好。
发现确实枚举可以。
从左到右枚举大小为K的区间
那么，把这个区间变成同一个数，每个数+1或者-1，必然都变成中位数（货仓选址问题）。
设中位数值是val，是第(k+1)/2个数
所以，我们可以维护这个区间。区间排好序的
为了方便查找操作次数，我们还要记录l~中位数的和s。
这样，放砖头的次数，就是val*((k+1)/2)-s
然后，扔砖头的次数，就是sum-val*(k-(k+1)/2)
sum可以直接记录。
滑动k区间的时候，要支持插入一个数，删除一个数。
所以
1.splay
注意，中位数可能有很多相同的。
但是一个前缀和必须限定是前(k+1)/2个。
讨论一下个数。（WA了几次）
#include<bits/stdc++.h> #define int long long #define ls t[x].ch[0] #define rs t[x].ch[1] using namespace std; typedef long long ll; const int N=100000+5; const ll inf=((1LL*1)<<62); int n,k; ll h[N]; ll ans; int pos; ll sum; ll to; struct node{ int ch[2]; ll sum,val; int sz,fa; int tot; void init(int f,ll v){ fa=f,val=v;sum=v,sz=1,tot=1; } }t[N]; int rt; int pc; void pushup(int x){ t[x].sz=t[ls].sz+t[rs].sz+t[x].tot; t[x].sum=t[ls].sum+t[rs].sum+t[x].tot*t[x].val; } void rotate(int x){ int y=t[x].fa,d=t[y].ch[1]==x; t[t[y].ch[d]=t[x].ch[!d]].fa=y; t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[1]==y]=x; t[t[x].ch[!d]=y].fa=x; pushup(y); } void splay(int x,int f){ while(t[x].fa!=f){ int y=t[x].fa,z=t[y].fa; if(z!=f) { rotate((t[y].ch[0]==x)==(t[z].ch[0]==y)?y:x); } rotate(x); } pushup(x); if(f==0) rt=x; } void insert(ll v){ if(!rt){ rt=++pc; t[rt].init(0,v);return; } int x=rt; while(1){ //cout<<" x "<<rt<<endl; t[x].sum+=v; t[x].sz++; if(t[x].val==v){ t[x].tot++; break; } int d=t[x].val<v; if(!t[x].ch[d]){ t[x].ch[d]=++pc; t[t[x].ch[d]].init(x,v); x=t[x].ch[d]; break; } x=t[x].ch[d]; } splay(x,0); } void remove(int v){ int goal=rt; while(t[goal].val!=v){ int d=t[goal].val<v; goal=t[goal].ch[d]; } splay(goal,0); t[goal].tot--; t[goal].sum-=v; t[goal].sz--; //pushup(goal); if(t[goal].tot) return; int son=t[goal].ch[1]; while(son&&t[son].ch[0]) son=t[son].ch[0]; if(!son){ rt=t[goal].ch[0]; t[rt].fa=0; } else{ splay(son,goal); t[t[son].ch[0]=t[goal].ch[0]].fa=son; t[rt=son].fa=0; pushup(rt); } } int kth(int k){ int u=rt; //cout<<" k , u"<<k<<" "<<u<<endl; while(1){ int d=k-t[t[u].ch[0]].sz; //cout<<" d "<<d<<endl; if(d<=0) u=t[u].ch[0]; else if(d>=1&&d<=t[u].tot) return u; else { k=d-t[u].tot; u=t[u].ch[1]; } } } signed main(){ //freopen("4.in","r",stdin); //freopen("haha.out","w",stdout); scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++) scanf("%lld",&h[i]); for(int i=1;i<=k;i++){ //cout<<" before "<<i<<endl; insert(h[i]);sum+=h[i]; }//cout<<" bug "<<endl; ans=inf; int hlf=(k+1)/2; //cout<<" hlf "<<hlf<<endl; // cout<<rt<<" "<<t[rt].ch[1]<<" "<<t[t[rt].ch[1]].ch[1]<<endl; for(int i=k;i<=n;i++){ int now=kth(hlf); splay(now,0); //cout<<" now "<<now<<endl; int v=t[now].val; ll zong=t[t[now].ch[0]].sum+(hlf-t[t[now].ch[0]].sz)*v; ll cos=v*hlf-zong; cos+=sum-zong-(k-hlf)*v; //cout<<i<<" : "<< "cos "<<cos<<" zong "<<zong<<" v "<<v<<endl; if(cos<ans){ ans=cos;pos=i; to=v; //cout<<" new "<<" i "<<i<<" "<<ans<<" "<<v<<endl; } sum-=h[i-k+1]; remove(h[i-k+1]); if(i+1<=n){ sum+=h[i+1]; insert(h[i+1]); } } //cout<<endl<<endl; printf("%lld ",ans); for(int i=1;i<=n;i++){ if(i>=pos-k+1&&i<=pos) printf("%lld ",to); else printf("%lld ",h[i]); } return 0; }
2.对顶堆，懒惰删除标记（手写堆）
动态维护中位数的经典做法。
一个大根堆维护前(1+k)/2的数，一个小根堆维护剩下的数。
插入就和大根堆堆顶比较，
删除开一个map记录这个数被删除了。
每次要调整，保证sz大>=sz小，且sz大<=sz小+1
取出大根堆的堆顶作为当前中位数的时候，判断这个数有没有被删除。
被删除的话，就先进行调整，然后再取出中位数。直到真正取出为止。
3.权值线段树
离散化权值，然后每个位置记录出现次数。为统计和，每个叶子贡献就是出现次数*实际的值。
然后找第(k+1)/2大即可。
插入删除单点修改。
总结：
1.对于一个区间长度有限制的问题，一般都是要枚举一个端点，或者单调队列等等
然后对于当前区间进行操作处理，区间移动的时候，单点修改即可维护。
2.对于区间都变成一个数的货仓选址问题还要熟悉。