概要

ランナーを初期位置 \(P_i\) の昇順に並べたとき、追い抜きの回数は「速度 \(V_i\) の逆転（転倒）数」と一致します。よって逆転数を高速に数える問題になります。

考察

重要な気づき

ランナー \(i, j\) について \(P_i < P_j\)（\(i\) が後方、\(j\) が前方）だとします。時刻 \(t\) の位置は - \(i\): \(P_i + V_i t\) - \(j\): \(P_j + V_j t\)

「追い抜き」が起きるのは、ある \(t>0\) で [ P_i + V_i t > P_j + V_j t ] となるときです。これを変形すると [ (V_i - V_j)t > P_j - P_i ] 右辺は \(P_j - P_i > 0\) なので、

• \(V_i > V_j\) なら、\(t = \dfrac{P_j - P_i}{V_i - V_j} > 0\) が存在し、必ず一度追い抜く
  
• \(V_i < V_j\) なら、左辺は常に \(\le 0\) で追い抜けない

制約より速度はすべて異なるため、同速で追い抜けない／同時刻に並走し続けるケースはありません。

つまり、追い抜き回数 =「初期位置の順番では後ろなのに、速度は速い」ペアの数 [ #{(i,j)\mid P_i < P_j \ \text{かつ}\ V_i > V_j} ] になります。

素朴解がダメな理由

全ペア \((i,j)\) を調べると \(O(N^2)\) で、\(N \le 2\times 10^5\) では到底間に合いません。

どう解決するか

\(P\) でソートして「初期位置の順番」を固定すると、問題は 速度列 \(V\) の逆転数（inversion） を数えるだけになります。逆転数は Fenwick 木（BIT）で \(O(N\log N)\) で求められます。

（例）\(P\) 昇順で見た速度が \([4,1,3]\) のとき、逆転は \((4,1),(4,3)\) の2つ → 追い抜き2回。

アルゴリズム

1. ランナーを初期位置 \(P_i\) の昇順にソートする。
2. その順に速度列 \(V_1,V_2,\dots,V_N\) を作る。
3. 速度は最大 \(10^9\) なので、そのまま BIT の添字にできません。
   そこで速度を昇順に並べて 座標圧縮し、各速度 \(V\) を \(1..N\) の順位（rank）に変換する。
4. 左から順に速度 rank を見ていき、BIT に「これまでに出た速度の個数」を記録する。
   • いま見ている速度 rank を \(r\) とする
   • これまでに見た個数を seen
   • BIT の前計算で「これまでに出た速度 \(\le r\) の個数」を leq = sum(r) とすると、
     • これまでに出た速度で 自分より大きい 個数は seen - leq
     • これがちょうど「逆転（=追い抜きになるペア）」の増分
   • その後 BIT に \(r\) を 1 個追加する

これで全体の逆転数（追い抜き回数）が求まります。

計算量

• 時間計算量: \(O(N\log N)\)（ソート2回 + BIT の更新/取得が \(N\) 回）
• 空間計算量: \(O(N)\)（配列・BIT・座標圧縮用）

実装のポイント

• 座標圧縮：速度はすべて異なるので rank = {v: i+1} の辞書で一意に対応できます（1-indexed にするのが BIT と相性が良い）。

• BIT の使い方：

  • sum(r) は「rank \(\le r\) の出現数」
  • seen - sum(r) が「rank \(> r\) の出現数」＝逆転の追加分

• 入力が大きいので sys.stdin.buffer.read() で高速に読み取っています。

  ソースコード

import sys

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n = data[0]
    runners = []
    idx = 1
    for _ in range(n):
        p = data[idx]; v = data[idx + 1]
        idx += 2
        runners.append((p, v))

    runners.sort()  # by position
    vs = [v for _, v in runners]

    sorted_vs = sorted(vs)
    rank = {v: i + 1 for i, v in enumerate(sorted_vs)}  # 1-indexed

    fw = Fenwick(n)
    inv = 0
    seen = 0
    for v in vs:
        r = rank[v]
        leq = fw.sum(r)
        inv += seen - leq
        fw.add(r, 1)
        seen += 1

    print(inv)

if __name__ == "__main__":
    main()

---

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