Come Together [全国統一プログラミング王決定戦本戦 C]

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_c

前提知識

• BIT
• 二分探索
• マンハッタン距離についての知識

解説

https://atcoder.jp/contests/nikkei2019-final/submissions/4312922

まず、この問題を考える糸口だが、「マンハッタン距離の総和の最小化問題である」という所から始める。
マンハッタン距離の問題について慣れている人であれば、

• マンハッタン距離の総和が最小となるのは中央値
• 縦横独立に考えられる

というのが瞬時に出てくる。
これが出てこないとこの問題を解くのは難しい。経験を要する問題。
　
ここまで分かれば、後は、中央値の求め方だ。
これは二分探索で求めることができる。
(全部の個数/2の切り上げ)+1番目が求めたい中央値となるので、
check(x) := x以上の数が(全部の個数/2の切り上げ)個以上か
という比較関数で二分探索すれば求められる。
個数を集計するにはBITを使おう（計算量的には累積和の方がいい。特にBITにした意味は無い）
　
これをX,Yどちらにもやって、最小となる部分が見つかったら、マンハッタン距離の総和を取ればいい。
自分は全部に駒があるとして、マンハッタン距離の総和を求めて、無い部分を引くことで実現している。

ll H, W, K, R[101010], C[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> K;
    rep(i, 0, K) cin >> R[i] >> C[i];
    rep(i, 0, K) R[i]--, C[i]--;
 
    ll tot = H * W - K;
    ll sx = -1, sy = -1;
    
    rep(_, 0, 2) {
        BIT<ll> bit(W);
        rep(x, 0, W) bit.add(x, H);
        rep(i, 0, K) bit.add(C[i], -1);
 
        ll ok = 0, ng = W;
        ll bor = (tot + 1) / 2;
        while(ok + 1 != ng) {
            ll md = (ng + ok) / 2;
            if (bor <= bit.get(md, W)) ok = md;
            else ng = md;
        }
        sx = ok;
 
        swap(H, W);
        swap(sx, sy);
        rep(i, 0, K) swap(R[i], C[i]);
    }
 
    ll ans = 0;
    rep(x, 0, W) ans += abs(x - sx) * H;
    rep(y, 0, H) ans += abs(y - sy) * W;
    rep(i, 0, K) ans -= abs(C[i] - sx) + abs(R[i] - sy);
    cout << ans << endl;
    
}