概要

各花壇を 1 つ取り除いたとき、残りの点が作る「異なる \(X\) の数」×「異なる \(Y\) の数」から点数を引いた空きセル数を、全ての花壇について高速に求めます。

考察

配置図のセル総数は「使われている \(X\) 座標の種類数」\(C_x\) と「使われている \(Y\) 座標の種類数」\(C_y\) によって \(C_x \times C_y\) と決まります。したがって、花壇を 1 つ消した後に必要なのは

• 消したことで \(X\) の種類数が減るか？（その \(X\) が他に残っているか）
• 消したことで \(Y\) の種類数が減るか？（その \(Y\) が他に残っているか）

の 2 点だけです。

素朴に各 \(i\) について「花壇 \(i\) を除いた集合」を作って毎回相異なる \(X, Y\) を数えると、毎回 \(O(N)\) かかり全体で \(O(N^2)\) となり、\(N \le 2 \times 10^5\) では間に合いません（TLE）。

ここでの重要な気づきは次です：

• ある花壇 \(i\) を取り除いたとき、\(X_i\) が その花壇でしか出現しない（出現回数が 1）なら \(C'_x = C_x - 1\)、そうでなければ \(C'_x = C_x\)
• \(Y\) についても同様に、\(Y_i\) の出現回数が 1 なら \(C'_y = C_y - 1\)、それ以外は変化なし

つまり、各座標値の出現回数（頻度）さえ分かれば、各 \(i\) の答えは \(O(1)\) で計算できます。

簡単な例： - 異なる \(X\) が 3 種類、異なる \(Y\) が 4 種類なら、元のセル総数は \(12\) - ある点を消して、その点の \(X\) が唯一なら \(X\) 種類は 2 に減る（そうでなければ 3 のまま） - 同様に \(Y\) 種類も判定し、\(C'_x \times C'_y - (N-1)\) を出すだけ

アルゴリズム

1. 全ての花壇について、\(X\) の出現回数 cntx[x] と \(Y\) の出現回数 cnty[y] を辞書（連想配列）で数える。
2. \(C_x = |\{X_i\}|\)、\(C_y = |\{Y_i\}|\) をそれぞれ辞書のキー数として求める。
3. 各花壇 \(i\) について以下を行う：
   • dx = 1 もし cntx[X_i] == 1（取り除くとその \(X\) が消える）なら、そうでなければ dx = 0
   • dy = 1 もし cnty[Y_i] == 1 なら、そうでなければ dy = 0
   • \(C'_x = C_x - dx\), \(C'_y = C_y - dy\)
   • 答えは \(C'_x \times C'_y - (N - 1)\)
4. 以上を \(i=1..N\) で出力する。

計算量

• 時間計算量: \(O(N)\)（頻度計数が \(O(N)\)、各 \(i\) の計算が \(O(1)\) で合計 \(O(N)\)）
• 空間計算量: \(O(N)\)（座標配列と辞書に最大 \(N\) 程度の要素）

実装のポイント

• 「取り除いたときに種類数が減るか」は「その値の出現回数が 1 かどうか」だけで判定できる。

• 座標値は \(-10^9\) 〜 \(10^9\) と大きいので、配列で直接管理せず辞書（Python の dict）でカウントする。

• 出力は "\n".join(...) でまとめて書くと高速です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    xs = [0] * N
    ys = [0] * N

    cntx = {}
    cnty = {}

    for i in range(N):
        x, y = map(int, input().split())
        xs[i] = x
        ys[i] = y
        cntx[x] = cntx.get(x, 0) + 1
        cnty[y] = cnty.get(y, 0) + 1

    Cx = len(cntx)
    Cy = len(cnty)

    out = []
    for i in range(N):
        dx = 1 if cntx[xs[i]] == 1 else 0
        dy = 1 if cnty[ys[i]] == 1 else 0
        Cx2 = Cx - dx
        Cy2 = Cy - dy
        out.append(str(Cx2 * Cy2 - (N - 1)))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。