Manhattan Center (manhattan-center) | CSA

与えられた頂点のK個からなる部分集合について、最適なPの座標はx座標の中央値となる。 なので、Pの候補は与えられた頂点のx座標に限られる。

これらx座標を昇順に見ていく。(以下、x[k]<x[k+1]とする)

P=x[0]としてとりあえず近いK個を集合Lに入れておく。残った頂点は集合Rに入っているとする。

x[k] -> x[k+1]と変化したとする。x[k]のときの最適な構成Lから、x[k+1]のときの最適な構成L'を得たい。そのために、Lから遠くなった頂点を取り除きつつ、Rの近くなった頂点を突っ込んでいく。

(xl, yl) ∈ L, (xr, yr) ∈ R, xl<=x[k]<=xrとすると yl + (x[k] - xl) > yr + (xr-x[k]) ならば(xl, yl)の代わりに(xr, yr)を使ったほうがよい。 そのため、yl-xlが最大となるような(xl, yl)とyr+xrが最小となるような(xr, yr)を比較していく。

あとはマンハッタン距離の和を動的に求めたい。y座標については総和を足し引きするだけ。Pの座標によらないため。x座標については、Binary Indexed Treeで座標ごとに座標の和、その座標の頂点数を数えておけば簡単。

int N, K;
cin >> N >> K;

priority_queue<pii, vector<pii>, greater<pii> > R;
priority_queue<pii> L;

vector<int> xs;
vi X(N), Y(N);
rep(i, N) {
    int x, y;
    cin >> x >> y;
    R.push(mp(y + x, i));
    X[i] = x;
    Y[i] = y;
    xs.push_back(x);
}
sort(all(xs));
xs.erase(unique(all(xs)), xs.end());

auto id = [&](int x) {
    RT (int)(lower_bound(all(xs), x) - xs.begin());
};

BIT bit(sz(xs)), cnt(sz(xs));
ll sm = 0, re = LLONG_MAX;
auto add = [&](int k) {
    sm += Y[k];
    L.push(mp(Y[k] - X[k], k));
    cnt.add(id(X[k]), 1);
    bit.add(id(X[k]), X[k]);
};

while (sz(L) < K && sz(R)) {
    auto q = R.top(); R.pop();
    int k = q.second;
    add(k);
}
each(p, xs) {
    while (sz(L) && sz(R)) {
        auto l = L.top();
        auto r = R.top();
        if (l.first + p > r.first - p) {
            R.pop();
            if (X[r.second] < p) {
                continue;
            }
            L.pop();
            add(r.second);

            sm -= Y[l.second];
            cnt.add(id(X[l.second]), -1);
            bit.add(id(X[l.second]), -X[l.second]);
        } else {
            break;
        }
    }
    ll z = cnt.sum(id(p)) * p - bit.sum(id(p));
    ll w = bit.sum(id(p), sz(xs)) - cnt.sum(id(p), sz(xs))*p;

    smin(re, z + w + sm);
}
cout << re << endl;