luogu 3466 对顶堆

显然答案是将一段区间全部转化成了其中位数
这样的话，需要维护一个数据结构支持查询当前所有数中位数
对顶堆
用两个堆
将 < 中位数的数放入大根堆
将 > 中位数的数放入小根堆
这样就会存在删除操作
删除的时候
由于无法快速删除
只需做个标记，标记该数被删除了一次
并且堆的实际大小也应该另外记录维护
在标记时需要更改相应的堆的大小与权值
答案就非常显然了

#include <bits/stdc++.h>

using namespace std;

#define gc getchar()

inline int read() {

    int x = ; char c = gc;

    while(c < '' || c > '') c = gc;

    while(c >= '' && c <= '') x = x *  + c - '', c = gc;

    return x;

}

#define Rep(i, a, b) for(int i = a; i <= b; i ++)

#define Fin(str) freopen(str, "r", stdin)

#define Fout(str) freopen(str, "w", stdout)

#define E return

#define LL long long

const int N = 1e5 + ;

int n, k;

int A[N], use[N * ];

priority_queue <int, vector<int>, less<int> > Big;

priority_queue <int, vector<int>, greater<int> > Small;

int Size1, Size2;

LL Sum1, Sum2;

void Update() {

    while(Big.size() && use[Big.top()]) use[Big.top()] --, Big.pop();

    while(Small.size() && use[Small.top()]) use[Small.top()] --, Small.pop();

}

void Out();

void Add(int x) {

    Update();

    while(Size1 < (k + ) /  && Small.size()) {

        int num = Small.top();

        Small.pop();

        Size1 ++, Sum1 += num;

        Size2 --, Sum2 -= num;

        Big.push(num);

        Update();

    }

    Update();

    if(Size1 < (k + ) / ) {

        Size1 ++, Sum1 += x, Big.push(x); return ;

    }

    Update();

    int num = Big.top();

    if(x < num) {

        Small.push(num);

        Big.pop();

        Size2 ++, Sum2 += num;

        Sum1 += (x - num);

        Big.push(x);

    } else {

        Size2 ++, Sum2 += x, Small.push(x);

    }

    Update();

}

void Del(int x) {

    use[x] ++;

    int top1 = Big.top();

    if(x <= top1) Size1 --, Sum1 -= x;

    else Size2 --, Sum2 -= x;

}

LL Calc() {

    Update();

    LL mid = Big.top();

    return 1ll * mid * Size1 - 1ll * Sum1 + 1ll * Sum2 - 1ll * mid * Size2;

}

int main() {

    n = read(), k = read();

    Rep(i, , n) A[i] = read();

    Rep(i, , k) Add(A[i]);

    LL Answer = Calc();

    int bef = ;

    int flag = k, mid = Big.top();

    Rep(i, k + , n) {

        Del(A[++ bef]);

        Add(A[i]);

        LL Ans = Calc();

        if(Ans < Answer) {

            flag = i, mid = Big.top();

            Answer = Ans;

        }

    }

    cout << Answer << "\n";

    Rep(i, , n) {

        if(i <= flag && i >= flag - k + ) {

            cout << mid << "\n";

        } else cout << A[i] << "\n";

    }

    return ;

}