Luogu 3466 [POI2008]KLO-Building blocks

题目链接：传送门
题目描述
N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作
1:从某柱砖的顶端拿一块砖出来,丢掉不要了.
2:从仓库中拿出一块砖,放到另一柱.仓库无限大.
现在希望用最小次数的动作完成任务.你还要输出结束状态时,每柱砖的高度
输入样例
5 3
3
9
2
3
1
输出样例
2
3
9
2
2
2

就是暴力枚举每一种长度为k的区间求它的代价就好了
你需要写一个支持插入、删除、区间第k大的数据结构
我这里用的fhq
解释在代码里

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <ctime>
#include <set>
#include <vector>
#include <iomanip>
#define A 1000010
#define B 2010

using namespace std;
typedef long long ll;
#define int ll //懒人必备
int ch[A][2], siz[A], val[A], cv[A], cnt, sum[A];
int n, k, a[A], l, r, opt, x, y, z, root, m, ans = 0x7fffffffffffff, ansl, ansm, ansr;
void update(int x) { //需要另外维护一个sum
    siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
    sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + val[x];
}
int newnode(int x) { //下面都是fhq的基本操作
    siz[++cnt] = 1;
    cv[cnt] = rand();
    val[cnt] = sum[cnt] = x;
    return cnt;
}
void split(int now, int k, int &x, int &y) {
    if (!now) {
        x = y = 0;
        return;
    }
    if (val[now] <= k) {
        x = now;
        split(ch[now][1], k, ch[now][1], y);
    }
    else {
        y = now;
        split(ch[now][0], k, x, ch[now][0]);
    }
    update(now);
}
int merge(int x, int y) {
    if (!x or !y) return x + y;
    if (cv[x] < cv[y]) {
        ch[x][1] = merge(ch[x][1], y);
        update(x);
        return x;
    }
    else {
        ch[y][0] = merge(x, ch[y][0]);
        update(y);
        return y;
    }
}
int kth(int now, int k) {
    if (k <= siz[ch[now][0]]) return kth(ch[now][0], k);
    else if (k == siz[ch[now][0]] + 1) return val[now];
    else return kth(ch[now][1], k - siz[ch[now][0]] - 1);
}
void insert(int a) {
    split(root, a, x, y);
    root = merge(merge(x, newnode(a)), y);
}
void dele(int a) {
    split(root, a, x, z);
    split(x, a - 1, x, y);
    y = merge(ch[y][0], ch[y][1]);
    root = merge(x, merge(y, z));
}

signed main(int argc, char const *argv[]) { //懒人必备signed
    srand(time(0));
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < k; i++) insert(a[i]); //先把前k个数插进去
    l = 0, r = k - 1; //两个“指针”
    for (int i = k; i <= n; i++) {
        l++; r++;
        dele(a[l - 1]), insert(a[r]); //维护新的序列
        if (k % 2) m = kth(root, k / 2 + 1); //这里不太敢用位运算
        else m = (kth(root, k / 2) + kth(root, k / 2 + 1)) / 2; //中位数的运算
        split(root, m, x, z); //把树分成小于m的和大于m的
        split(x, m - 1, x, y);
        int size1 = siz[x], size2 = siz[z]; //小于m的数的代价用中位数乘它们的个数减去它们的和
        int sum1 = sum[x], sum2 = sum[z]; //大于m的数的代价用它们的和减去中位数乘它们的个数
        root = merge(x, merge(y, z));
        int xx = size1 * m - sum1, yy = sum2 - m * size2;
        int tmp = xx + yy; //加起来更新答案
        if (tmp < ans) {
            ans = tmp;
            ansm = m; //更新答案边界
            ansl = l; //ansl和ansr就是最优解所在的位置
            ansr = r;
        }
    }
    cout << ans << endl;
    // cout << ansl << \" \" << ansm << \" \" << ansr << endl;
    for (int i = 1; i < ansl; i++) cout << a[i] << endl; //挑着输出
    for (int i = ansl; i <= ansr; i++) cout << ansm << endl;
    for (int i = ansr + 1; i <= n; i++) cout << a[i] << endl;
    return 0;
}