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;