概要

\(N\) 人のランナーの初期位置と速度が与えられる。早い人から遅い人を追い越す回数（＝追い抜き）を数える問題。

考察

まず、「追い抜き」とは何なのかを正確に理解することが大切です。
時刻 \(t=0\) でランナー \(i\) がランナー \(j\) よりも後方にいる（つまり \(P_i < P_j\)）ときに、
後に \(t>0\) で \(P_i + V_i \cdot t > P_j + V_j \cdot t\) となる瞬間があるとき、
\(i\) が \(j\) を追い抜いたといいます。

これは言い換えれば、「初期位置の前後関係」と「速度の前後関係が入れ替わる」現象です。
つまり、初期位置順に並べたときに、その中で速度が「逆順」になっている組の数を数えればよいのです。

例えば、初期位置の順番が \(A, B, C\) だったとして、それぞれの速度が \(C > A > B\) なら、
\(A\) が \(B\) を追い越して、\(C\) が \(A, B\) の両方を追い越すので、合計 3 回の追い抜きがあります。

このように、初期位置順に並べた列の中で「自分より前にあって、自分のほうが速い」ランナーの数を数えるのは、転倒数（Inversion Number）を数える問題に帰着できます。
しかし、単純に全探索すると \(O(N^2)\) かかり、制約 \(N \leq 2 \times 10^5\) では間に合いません。

そこで、効率的に転倒数を数える方法として、Fenwick Tree（Binary Indexed Tree） を用います。これにより \(O(N \log N)\) で求めることができます。

アルゴリズム

1. 各ランナーについて、初期位置 \(P_i\) と速度 \(V_i\) を読み込む。
2. ランナーを初期位置の昇順に並べたときのインデックス列を得る（pos_sorted）。
3. ランナーを速度の昇順に並べたときのインデックス列を得る（vel_sorted）。
4. 各ランナーに対して「速度の順位（速いほど順位が低い）」を計算し、vel_rank 配列に記録する。
5. 初期位置順に並んだランナーたちの「速度の順位」だけを取り出したリスト ranks を作る。
6. この ranks の転倒数を Fenwick Tree を使って高速に計算する：
   • 後ろから見ていく。
   • 現在の要素より小さい順位の個数をBITで数える → 追い抜き数に加算。
   • 自分の順位をBITに追加する。
7. 最終的な転倒数が答え。

例

入力:

3
1 3
3 1
2 2

初期位置順：ランナー1(1m), ランナー3(2m), ランナー2(3m)
速度順位：ランナー2(1m/s): 0位, ランナー3(2m/s): 1位, ランナー1(3m/s): 2位

ranks = [2, 1, 0]

この列の転倒数は： - 2より右にある1, 0 → 2つ - 1より右にある0 → 1つ → 合計 3 が答え

計算量

• 時間計算量: \(O(N \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• ランナーのインデックスをキーにして、初期位置・速度それぞれでソートする。
• Fenwick Tree では1-indexedで扱うため、add(rank + 1, 1)のように+1する必要がある。
• 転倒数の計算では後ろから処理することで、すでに見た要素をBITに入れておける。

## ソースコード

```python
import sys
from operator import itemgetter

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    runners = []
    for i in range(N):
        p = int(data[2*i + 1])
        v = int(data[2*i + 2])
        runners.append((p, v))
    
    # 初期位置でソートしたインデックス
    pos_sorted = sorted(range(N), key=lambda i: runners[i][0])
    # 速度でソートしたインデックス
    vel_sorted = sorted(range(N), key=lambda i: runners[i][1])
    
    # 速度順位を計算（速いほどrankが小さい）
    vel_rank = [0] * N
    for rank, idx in enumerate(vel_sorted):
        vel_rank[idx] = rank
    
    # 初期位置順で並べた時の速度順位のリスト
    ranks = [vel_rank[i] for i in pos_sorted]
    
    # 転倒数を計算する（Fenwick Tree使用）
    class FenwickTree:
        def __init__(self, n):
            self.n = n
            self.tree = [0] * (n + 1)
        
        def add(self, i, x):
            while i <= self.n:
                self.tree[i] += x
                i += i & -i
        
        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s
    
    ft = FenwickTree(N)
    inv_count = 0
    for i in range(N-1, -1, -1):
        rank = ranks[i]
        inv_count += ft.sum(rank)
        ft.add(rank + 1, 1)
    
    print(inv_count)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。