平らな農地 [yukicoder No.738] - はまやんはまやんはまやん

考察過程

1. かかるコストはマンハッタン距離になっている
2. 定石「マンハッタン距離の総和を最小化したいときは中央値を使う」
3. K個連続した要素を全探索して、すべて中央値にしたときのコストの最小値が答え
4. 中央値を求めるにはBIT+座圧+二分探索でできる
5. 長方形区間での総和を求める計算は、セグ木にセグ木を乗せたデータ構造を使えばいい
6. 計算量も怪しいけど大丈夫では？

解法

https://yukicoder.me/submissions/288515

K個連続した区間で
1. 中央値を求める
2. 長方形区間総和を求める
をO(logN)くらいで実現できれば、この問題は解ける。
　
1. 中央値を求める
座圧しておき、BITに載せられるようにしておく。
K個連続した区間で現れる数をBITに入れておく。
すると、中央値はK/2番目の数なので、二分探索で[0,x]の範囲でK/2個より大きい境目のxを探す。
するとx-1番目の数が中央値。
　
2. 長方形区間総和を求める
これはセグメントツリーにセグメントツリーを乗せる手法を使おう。
実装が大変なのでライブラリ化しておこう。
これで解ける。

※ はむこさんのWaveletMatrix解法が驚くほどスマート

int N, K, A[101010], M;
BIT<int> bit(101010);
StaticHealthy2DSegTree st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];

    vector<int> dic;
    rep(i, 0, N) dic.push_back(A[i]);
    sort(all(dic));
    dic.erase(unique(all(dic)), dic.end());
    M = dic.size();

    vector<vector<pair<int, ll>>> v(N);
    rep(i, 0, N) {
        int y = lower_bound(all(dic), A[i]) - dic.begin();
        v[i].push_back({y, A[i]});
        A[i] = y;
    }
    st.init(v);

    ll ans = infl;
    rep(i, 0, K) bit.add(A[i], 1);
    rep(L, 0, N - K + 1) { // [L,R)
        int R = L + K;

        int ng = 0, ok = M;
        while (ng + 1 != ok) {
            int md = (ng + ok) / 2;
            if (K / 2 < bit.get(0, md)) ok = md;
            else ng = md;
        }
        ok--;

        ll cent = dic[ok];
        ll low = st.get(L, R, 0, ok);
        ll high = st.get(L, R, ok + 1, inf);
        ll cst = bit.get(0, ok) * cent - low + high - bit.get(ok + 1, M) * cent;
        chmin(ans, cst);

        bit.add(A[L], -1);
        bit.add(A[R], 1);
    }

    cout << ans << endl;
}