Moving the Kings | HourRank 27

キングが中心にいる場合、キングから周囲のマスまでの移動は

22222
21112
21012
21112
22222

のようになっている。距離1のマスは45度回転すると のようになる。 すべて整数で表すために√2を掛けると 座標は(2, 0), (1, 1), (0, 2), (-1, 1), (-2, 0), (-1, -1), (0, -2)へと移動する。 つまりもともと移動1だったマスは以下のように分布する。

..O..
.O.O.
O.X.O
.O.O.
..O..

これはキングからのマンハッタン距離が2であるマスである。同様に移動kのマスはマンハッタン距離2kのマスへ移動する。 マンハッタン距離は

|x-x'| + |y-y'|

のように求められるから、解はマンハッタン距離の和を2で割ったもの。座標変換は

|1  -1|
|1   1|

のような行列を掛ければいい。これは45度回転の行列に√2を掛けたもの。

x -> x-y
y -> x+y

を得た。 さてあとはΣ|x-x'|とΣ|y-y'|の求め方になる。 これらは別々かつ同様に求められるのでΣ|x-x'|だけ考える。 とりあえずキングの座標とクエリの座標をソートしておく。 まず最左のクエリの座標について解を求める。クエリを座標の昇順に見る。クエリの座標q1<=q2について考える。q1については解を計算済みとする。キングの座標をpxとする

(1)px<=q1のとき

キングから離れる。各キングについてq2-q1だけ距離が増す。

(2)q2 > pxのとき

キングに近づく。各キングについてq2-q1だけ距離が減る。

(3) q1 < px <= q2のとき 個別に計算する

したがって、クエリを昇順に見るのと並行して、尺取法で境目のキングを座標の昇順に見ていく。更に、現在見ている座標より左にいるキング、右にいるキングをそれぞれ数えておいて増減させる。

int N, Q;

vll f(vll &p, vll &q) {
    vll res(Q);
    // (q[i], i)
    vector<pair<ll, int> > qi(Q);
    rep(i, Q) {
        qi[i] = mp(q[i], i);
    }
    sort(all(p));
    sort(all(qi));

    ll S = 0;
    ll nl = 0, nr = 0;
    rep(i, N) {
        ll z = qi[0].first;
        S += abs(p[i] - z);
        if (p[i] <= z)nl++;
        else nr++;
    }
    res[qi[0].second] = S;

    ll lb = nl, ub = nl;
    FOR(i, 1, Q) {
        ll z;
        int k;
        tie(z, k) = qi[i];
        ll pre = qi[i - 1].first;
        while (ub < N && p[ub] <= z) {
            S -= abs(pre - p[ub]);
            S += abs(z - p[ub]);
            nr--, ub++;
        }
        S += (nl - nr) * (z - pre);
        nl += ub - lb;
        lb = ub;
        res[k] = S;
    }
    return res;
}

void g(ll &x, ll &y) {
    ll xx = x - y, yy = x + y;
    x = xx; y = yy;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    cin >> N >> Q;
    vll px(N), py(N), qx(Q), qy(Q);
    rep(i, N)cin >> px[i] >> py[i], g(px[i], py[i]);
    rep(i, Q)cin >> qx[i] >> qy[i], g(qx[i], qy[i]);
    vll z = f(px, qx), w = f(py, qy);
    rep(i, Q) {
        ll ans = (z[i] + w[i]) / 2;
        cout << ans << endl;
    }
}