概要

\(N\) 人の中から \(2\) 人を選ぶ組 \((i,j)\) のうち、\(A_i+A_j \ge X\) かつ \(B_i+B_j \ge Y\) を満たすものの個数を数える問題です。\(N \le 10^5\) なので全ペア列挙（\(O(N^2)\)）では間に合わず、ソート＋二分探索＋BIT（フェニック木） で \(O(N\log N)\) に落とします。

考察

素朴な方法

すべての組 \((i,j)\) を二重ループで調べると、組の個数は約 \(\frac{N^2}{2} = 5\times 10^9\) 個になり、確実に TLE します。

条件を「片方を固定した数え上げ」に変形する

部員 \(i\) を固定すると、条件は

• \(A_j \ge X - A_i\)
• \(B_j \ge Y - B_i\)

という「\(j\) に関する 2 つの下限条件」になります。つまり平面上の点 \((A_j,B_j)\) のうち、右上の四分領域に入る点の個数を数える問題（2 次元 dominance counting）です。

条件が 1 つだけ（例えば \(A\) のみ）なら、\(A\) をソートして二分探索するだけで数えられます。しかし条件が 2 つあると、単純なソートだけでは「\(A\) の条件を満たす集合の中で \(B\) の条件も満たす個数」が分からないため、工夫が必要です。

解決の方針：片方をソート順で処理、もう片方を BIT で管理

点を \(A\) の昇順にソートしておきます。すると \(i\) を \(A\) の小さい順に見ていったとき、

\[\text{閾値 } thr = X - A_i\]

は単調に減少します。したがって「\(A_j \ge thr\) を満たす \(j\) の集合」は、ソート後の配列の末尾からの連続区間（接尾辞）であり、\(i\) が進むにつれてこの区間は広がるだけです（縮まない）。

そこで、尺取り法（two pointer）で「\(A\) の条件を満たす点」を順次 BIT に追加していき、追加済みの点の中から \(B_j \ge Y - B_i\) となるものの個数を BIT で数えれば、各 \(i\) について \(O(\log N)\) で答えが求まります。

重複と自分自身の処理

この数え方では、\((i,j)\) と \((j,i)\) の両方（順序付きペア）が数えられます。また、\(j=i\) 自身も条件を満たす場合（\(2A_i \ge X\) かつ \(2B_i \ge Y\)）にカウントされてしまいます。よって

\[\text{答え} = \frac{(\text{数えた総数}) - (\text{自分自身が条件を満たす人数})}{2}\]

とすればよいです。条件が \(i,j\) について対称なので、この式が成り立ちます。

アルゴリズム

1. 点 \((A_i,B_i)\) を \(A\) の昇順にソートし、配列 A, B を作る。
2. B の値を座標圧縮する（値が \(10^9\) まであるので BIT の添字にできない）。us = B のソート済み重複除去列、rank[i] = B[i] の順位（1-indexed）。
3. BIT（サイズ \(m=|us|\)、各位置の個数を管理）を用意し、ポインタ p = n（挿入済みは p 以降）とする。
4. \(i = 0,1,\dots,N-1\) の順に：
   • thr = X - A[i] として、A[p-1] >= thr の間 p を減らし、その点の rank を BIT に \(+1\) 挿入する。
   • t = Y - B[i] として、idx = bisect_left(us, t)（= \(B < t\) の値の個数）を求め、BIT で「\(B < t\) の挿入済み点数」 s を求める。
   • 挿入済み総数は n - p なので、条件を満たす個数は (n - p) - s。これを total に足す。
5. \(2A_i \ge X\) かつ \(2B_i \ge Y\) となる \(i\) の個数 self_ を数える。
6. (total - self_) // 2 を出力する。

具体例

\(N=3, X=5, Y=5\)、点が \((1,4),(3,3),(4,2)\)（すでに \(A\) 昇順）のとき：

• \(i=0\)：\(thr=4\) → \((4,2)\) を挿入。\(t=5-4=1\) → \(B\ge1\) は 1 個。total=1
• \(i=1\)：\(thr=2\) → \((3,3)\) を挿入（挿入済み \(\{2,3\}\)）。\(t=2\) → 2 個。total=3
• \(i=2\)：\(thr=1\) → \((1,4)\) を挿入（挿入済み \(\{2,3,4\}\)）。\(t=3\) → \(B\ge3\) は 2 個。total=5
• 自分自身：\((3,3)\) のみ（\(6\ge5, 6\ge5\)）→ self_=1
• 答え：\((5-1)/2 = 2\)

実際、条件を満たすのは \(\{(1,4),(4,2)\}\)（和 \(5,6\)）と \(\{(3,3),(4,2)\}\)（和 \(7,5\)）の 2 組で一致します。

計算量

• 時間計算量: \(O(N \log N)\)（ソート、座標圧縮の二分探索、BIT の各操作が \(O(\log N)\)、p の移動は全体で \(N\) 回）
• 空間計算量: \(O(N)\)

実装のポイント

• ポインタ p は巻き戻さない：A を昇順ソートしたことで閾値が単調減少するため、p は単調に減るだけです。これにより挿入回数は合計 \(N\) 回で済みます。もし逆順にソートしてしまうと単調性が崩れるので注意。

• 座標圧縮：\(B_i \le 10^9\) なので BIT の添字に直接使えません。sorted(set(B)) で圧縮し、bisect_left で順位を得ます。

• 「\(B \ge t\)」の数え方：BIT は「先頭からの累積和」が得意なので、まず idx = bisect_left(us, t)（= 圧縮後で \(B<t\) となる位置数）を求め、BIT の \([1,\,idx]\) の和 s = 「\(B<t\) の挿入済み個数」を計算し、(挿入済み総数) - s とします。\(t \le 0\) でも idx = 0 になり正しく全件が数えられます。

• 順序付き→無序への変換：最後に自己ペアを引いて 2 で割るのを忘れないこと。\(X,Y\) は最大 \(2\times10^9\) で \(2A_i\) も同様に大きいので、C++ 等では 64bit 整数を使う必要があります（答えも最大約 \(5\times10^9\)）。

• 高速入力：\(N=10^5\) 行の入力なので、Python では sys.stdin.buffer.read().split() で一括読み込みすると安全です。BIT も関数呼び出しを避けてループを直書きすると高速です。

  ソースコード

import sys
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); X = int(data[1]); Y = int(data[2])
    pts = sorted((int(data[3 + 2 * i]), int(data[4 + 2 * i])) for i in range(n))
    A = [p[0] for p in pts]
    B = [p[1] for p in pts]

    us = sorted(set(B))
    m = len(us)
    rank = [bisect_left(us, b) + 1 for b in B]

    tree = [0] * (m + 1)
    p = n
    total = 0
    for i in range(n):
        thr = X - A[i]
        while p > 0 and A[p - 1] >= thr:
            p -= 1
            k = rank[p]
            while k <= m:
                tree[k] += 1
                k += k & -k
        t = Y - B[i]
        idx = bisect_left(us, t)
        s = 0
        k = idx
        while k > 0:
            s += tree[k]
            k -= k & -k
        total += (n - p) - s

    self_ = 0
    for i in range(n):
        if 2 * A[i] >= X and 2 * B[i] >= Y:
            self_ += 1

    sys.stdout.write(str((total - self_) // 2) + "\n")

main()

---

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