洛谷 P3466 [POI2008]KLO-Building blocks 支持删除的堆

题面
这题怎么人均$fhq$啊，让$STL$选手情何以堪？

于是就来一发$priority$_$queue$+map的题解吧（突然发现map好慢啊）。

思路上面几位都说得比较清晰了，就是动态维护中位数，然后每次求最小代价，当时我脑袋一热，就想到了对顶堆，就是定义1个小根堆和1个大根堆，每次判断当前的数如果小于大根堆顶，就加入大根堆，否则加入小根堆，这样的话大根堆里的所有的数都比小根堆里的数小了，维护2个堆的大小相差不超过1后，就可以很容易取出中位数了。于是码码码之后发现：

好像要支持删除啊…

不过还有办法，支持搞出删除的堆的套路有2种（pb_ds的走开）：

一是把删除的数塞到另一个堆里面，如果2个堆顶相同，就同时删除（注意必须都是小根堆或大根堆）

第二是把数直接放入$map$中，每次取出时要特判。

本来本蒟蒻用的是$map$，结果不开$O_2$勇夺最优解倒数第二，实在是不敢看，所以改成了第一种方法。因为对顶堆是一个大根堆一个小根堆，所以删除的堆也要2个。

然后是计算代价的部分了，我们因为是计算绝对值，所以我们是不能把区间的数加起来再减去中位数乘区间数的。但是也好办，我们只要统计大根堆中的数的和$su{m}_1$,数的个数$siz{e}_1$以及小根堆的数的和$su{m}_2$,数的个数$siz{e}_2$,那么代价为：
$$Cost=mid?siz{e}_1?su{m}_1+su{m}_2?mid?siz{e}_2$$
原因也很好理解，因为大根堆中的数都小于等于中位数，所以可以一起加减，小根堆的数都大于等于中位数，所以同理。

代码（开$O_2$后跑到了最优解$Rank1$)：

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define int long long
//答案可能会爆int
inline void read(int &x){
    x=0;int fh=1;char c=getchar();while(c>'9'||c<'0'){
    if(c=='-')fh=-1; c=getchar();}while('0'<=c&&c<='9'){
    x=x*10+c-48;c=getchar();}x*=fh;
}//快读
inline int max(int a,int b){
    return a>b?a:b;}
inline int min(int a,int b){
    return a<b?a:b;}
priority_queue<int>Q1,Q2,D1,D2;
//分别表示大根堆、小根堆、用于删除的2个堆
//因为本蒟蒻记不住pq的格式，就把Q2里的数全部加负号来当成小根堆用，所以下文也会加负号还原
int n,k,a[100005],siz1,siz2,sum1,sum2,ans,Begin,ANS;
//siz1和siz2表示在Q1和Q2中有多少数应被删除但还在堆里
void balance(){
    while(Q1.size()-siz1>Q2.size()-siz2+1){
    if(!D1.empty()&&D1.top()==Q1.top()){
    D1.pop();Q1.pop();siz1--;continue;}sum2+=Q1.top();sum1-=Q1.top();Q2.push(-Q1.top());Q1.pop();}while(Q1.size()-siz1<Q2.size()-siz2){
    if(!D2.empty()&&D2.top()==Q2.top()){
    D2.pop();Q2.pop();siz2--;continue;}sum1+=-Q2.top();sum2-=-Q2.top();Q1.push(-Q2.top());Q2.pop();}}
//保持2个堆的平衡，为了方便，我们钦定大根堆数量大于等于小根堆数量，那么我们取中位数就可以在大根堆里取了
signed main(){
    ans=1e17;read(n);read(k);for(int i=1;i<=n;++i)read(a[i]);for(int i=1;i<=n;++i){
    if((!Q1.empty()&&a[i]>Q1.top())){
    Q2.push(-a[i]);sum2+=a[i];}else {
    Q1.push(a[i]);sum1+=a[i];}balance();if(i>=k){
    int mid=-1;while(mid==-1){
    balance();if(Q1.size()-siz1>=Q2.size()-siz2){
    if(!D1.empty()&&D1.top()==Q1.top()){
    D1.pop();Q1.pop();siz1--;}else mid=Q1.top();}}//找中位数if(ans>(Q1.size()-siz1)*mid-sum1+sum2-(Q2.size()-siz2 )*mid){
    ans=(Q1.size()-siz1)*mid-sum1+sum2-(Q2.size()-siz2 )*mid;Begin=i-k+1;ANS=mid;}//求最小代价if(Q1.top()>=a[i-k+1]){
    siz1++;D1.push(a[i-k+1]);sum1-=a[i-k+1];}else{
    siz2++;D2.push(-a[i-k+1]);sum2-=a[i-k+1];}//删除}}printf("%lld\n",ans);for(int i=1;i<=n;++i)if(i>=Begin&&i<Begin+k)printf("%lld\n",ANS);else printf("%lld\n",a[i]);return 0;
}