概要

\(N\) 人の生徒の得点が \(Q\) 回更新されるたびに、ソート済み列の \(\lceil N/2 \rceil\) 番目の値（基準値）を求め、基準値未満の生徒の人数を答える問題です。

考察

問題の整理

まず基準値の定義を確認します。\(N\) 人の得点を小さい順に並べたとき、\(\lceil N/2 \rceil\) 番目の値が基準値です。例えば：

• \(N = 5\) のとき \(\lceil 5/2 \rceil = 3\) → 小さい方から3番目
• \(N = 4\) のとき \(\lceil 4/2 \rceil = 2\) → 小さい方から2番目

補習対象は得点が厳密に基準値未満の生徒です（基準値と同じなら対象外）。

素朴なアプローチとその問題点

更新のたびに全得点をソートし直すと、1回のソートに \(O(N \log N)\) かかり、\(Q\) 回で \(O(QN \log N)\) となります。\(N, Q\) が最大 \(2 \times 10^5\) の場合、これでは間に合いません。

効率化のアイデア

得点の集合を常にソートされた状態で管理できれば、要素の削除・追加・k番目の取得・ある値未満の個数の取得がすべて高速に行えます。これには平衡二分探索木に相当するデータ構造が必要です。

Python では sortedcontainers ライブラリの SortedList がまさにこれを提供しており、各操作が \(O(\log N)\) で行えます。

アルゴリズム

1. 初期化: 全生徒の得点を SortedList に追加する。各生徒の現在の得点を配列 \(S\) で管理する。
2. \(k = \lceil N/2 \rceil\) を事前計算しておく。
3. 各更新 \((T_j, V_j)\) に対して：
   • 生徒 \(T_j\) の旧得点を SortedList から削除する。
   • 新得点 \(V_j\) を SortedList に追加する。
   • 配列 \(S[T_j]\) を \(V_j\) に更新する。
   • SortedList の \((k-1)\) 番目（0-indexed）の要素が基準値。
   • bisect_left(baseline) で基準値未満の要素数を求める。これが補習対象の人数。

具体例

\(N=5\), 得点が \([50, 30, 70, 20, 60]\) の場合： - ソート済み列: \([20, 30, 50, 60, 70]\) - \(k = 3\) なので基準値は \(50\)（0-indexed で \([2]\)） - 基準値 \(50\) 未満の要素は \(20, 30\) の \(2\) 個 → 補習対象は \(2\) 人

ここで生徒3の得点が \(70 \to 40\) に変わると： - ソート済み列: \([20, 30, 40, 50, 60]\) - 基準値は \(40\) - \(40\) 未満は \(20, 30\) の \(2\) 個 → 補習対象は \(2\) 人

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • 初期化で \(N\) 回の追加（各 \(O(\log N)\)）、各クエリで削除・追加・インデックスアクセス・二分探索がそれぞれ \(O(\log N)\)
• 空間計算量: \(O(N)\)
  • SortedList と得点配列の保持

実装のポイント

• 0-indexed と 1-indexed の変換: \(k = \lceil N/2 \rceil\) は1-indexed なので、SortedList からは sl[k-1] でアクセスする。

• 旧得点の管理: 更新時に SortedList から旧得点を削除する必要があるため、配列 \(S\) で各生徒の現在の得点を常に記録しておく。

• bisect_left の活用: sl.bisect_left(baseline) は、baseline 未満の要素数を返す（baseline と等しい要素は含まない）。これがそのまま補習対象の人数になる。

• 高速入出力: \(N, Q\) が大きいため、sys.stdin.buffer.read() でまとめて読み込み、出力も '\n'.join() でまとめて書き出す。

  ソースコード

import sys
from sortedcontainers import SortedList

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    S = [0] * (N + 1)
    sl = SortedList()
    
    for i in range(1, N + 1):
        S[i] = int(input_data[idx]); idx += 1
        sl.add(S[i])
    
    out = []
    k = (N + 1) // 2  # ceil(N/2), 1-indexed position
    
    for _ in range(Q):
        t = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        
        old_val = S[t]
        sl.remove(old_val)
        sl.add(v)
        S[t] = v
        
        # baseline is sl[k-1] (0-indexed)
        baseline = sl[k - 1]
        
        # count of elements strictly less than baseline
        count = sl.bisect_left(baseline)
        
        out.append(str(count))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

この解説は claude4.6opus-thinking によって生成されました。