概要

\(N\) 人の生徒の得点のうち、小さい方から \(\lceil N/2 \rceil\) 番目の値を「基準値」としたとき、その基準値より厳密に小さい得点の生徒が何人いるかを求める問題です。得点の更新が \(Q\) 回行われるため、各更新のたびに効率よく人数を計算する必要があります。

考察

1. 基準値と補習対象者の定義

生徒の得点を昇順に並べた列を \(A_1, A_2, \dots, A_N\) とすると、基準値は \(k = \lceil N/2 \rceil\) 番目の値 \(A_k\) です。 補習対象となるのは「得点が \(A_k\) 未満」の生徒です。

例えば、\(N=5\) のとき \(k=3\) です。得点が \(\{10, 20, 20, 30, 40\}\) ならば、基準値は \(A_3 = 20\) です。\(20\) 未満の得点は \(\{10\}\) のみなので、補習対象者は \(1\) 人となります。 ここで重要なのは、「基準値 \(A_k\) 未満の人数」は、得点をソートした状態において「値が \(A_k\) よりも手前にある、自分自身を含まない要素の数」と言い換えられる点です。

2. 素朴なアプローチの問題点

各更新ごとに得点をソートし直して \(A_k\) を探し、人数を数えると、1回の更新に \(O(N \log N)\) の時間がかかります。全体で \(O(QN \log N)\) となり、 \(N, Q \le 2 \times 10^5\) の制約下では実行時間制限に間に合いません。

3. 効率的な管理方法

得点の分布（どの点数に何人いるか）を高速に更新・取得できるデータ構造が必要です。 しかし、得点の値自体は最大 \(10^9\) と非常に大きいため、そのまま配列の添字として使うことはできません。そこで、以下の2つの工夫を組み合わせます。

1. 座標圧縮: 登場する可能性のあるすべての得点（初期スコアと更新後のスコアのすべて）を事前に列挙し、小さい順に \(1, 2, 3, \dots\) と番号を割り振ることで、扱う値の範囲を \(O(N+Q)\) に収めます。
2. フェニック木（Binary Indexed Tree / BIT）: 各得点（圧縮後の番号）に何人の生徒がいるかを管理します。
   • 特定の値までの累積和（ある点数以下の人数）を \(O(\log(N+Q))\) で取得。
   • 特定の値の人数更新を \(O(\log(N+Q))\) で実行。
   • BIT上での二分探索（Binary Lifting） を用いることで、「累積和が \(k\) 未満となる最大のインデックス」を \(O(\log(N+Q))\) で見つけることができます。この累積和こそが、求める「基準値未満の人数」に他なりません。

アルゴリズム

1. 座標圧縮の準備: 初期状態の全得点 \(S_i\) と、更新で現れる全得点 \(V_j\) を一つのリストにまとめ、重複を排除してソートします。各得点をその順位（1-indexed）に変換する辞書を作成します。
2. BITの初期化: 圧縮後の得点に基づき、各得点の出現頻度を BIT に登録します。
3. 更新とクエリの処理: 各更新 \((T_j, V_j)\) について：
   • 生徒 \(T_j\) の元の得点（の圧縮インデックス）を BIT から \(1\) 減算する。
   • 生徒 \(T_j\) の新しい得点 \(V_j\)（の圧縮インデックス）を BIT に \(1\) 加算する。
   • BIT 上で二分探索を行い、累積和が \(k = \lceil N/2 \rceil\) 未満である最大の範囲を探します。その時の累積和が答えとなります。

計算量

• 時間計算量: \(O((N + Q) \log (N + Q))\)
  • 座標圧縮のためのソートに \(O((N + Q) \log (N + Q))\) かかります。
  • 各更新において、BIT の更新と二分探索が \(O(\log(N + Q))\) で行われるため、全体で \(O(Q \log (N + Q))\) です。
• 空間計算量: \(O(N + Q)\)
  • 座標圧縮用のマップや BIT、現在の得点を保持する配列に \(O(N + Q)\) のメモリを使用します。

実装のポイント

• BIT上の二分探索: 通常、BIT で \(k\) 番目の要素を探す際は「累積和が \(k\) 以上になる最小のインデックス」を探しますが、この問題では「累積和が \(k\) 未満である最大の累積和」を直接求めることで、基準値未満の人数を一度に取得できます。

• 高速な入出力: Python の場合、input() ではなく sys.stdin.read().split() などを用いて一括で入力を読み込み、sys.stdout.write で出力することで、入出力によるボトルネックを回避できます。

• 更新がない場合の最適化: 同じ生徒が同じ得点に更新される場合、BIT を操作する必要はありません。前回の結果を再利用することで定数倍の高速化が可能です。

  ソースコード

import sys

# The problem asks for the number of students who have scores strictly less than the criterion value.
# The criterion value is the ceil(N/2)-th smallest score among N students.
# Since N and Q are up to 2e5, we need an efficient way to track scores and find the threshold.
# Coordinate compression combined with a Fenwick tree (Binary Indexed Tree) allows us to:
# 1. Update scores in O(log(N+Q)) time.
# 2. Find the k-th smallest value and its prefix sum in O(log(N+Q)) time using binary lifting.

def solve():
    # Fast I/O: read all input at once and split into tokens
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: number of students, Q: number of updates
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # S: initial scores of N students
    S = list(map(int, input_data[2:2+N]))
    
    # Updates: student number T and new score V for each of Q updates
    updates_raw = input_data[2+N:]
    T = list(map(int, updates_raw[0::2]))
    V = list(map(int, updates_raw[1::2]))
    
    # Coordinate Compression:
    # Gather all unique scores from initial data and updates to map them to a smaller range [1, M].
    coords = sorted(list(set(S) | set(V)))
    val_to_idx = {v: i + 1 for i, v in enumerate(coords)}
    M = len(coords)
    
    # Fenwick Tree (BIT) to maintain the frequency of scores
    bit = [0] * (M + 1)
    
    # Map initial scores to compressed indices and populate the BIT
    current_scores_idx = [val_to_idx[s] for s in S]
    for idx in current_scores_idx:
        bit[idx] += 1
        
    # Initialize the BIT in O(M) time
    for i in range(1, M + 1):
        j = i + (i & -i)
        if j <= M:
            bit[j] += bit[i]
            
    # k: the position of the criterion value in the sorted list of scores
    k = (N + 1) // 2
    
    # Prepare for binary lifting on the BIT
    bit_len = M.bit_length()
    powers = [1 << i for i in range(bit_len)]
    bit_len_range = range(bit_len - 1, -1, -1)
    
    # Pre-convert update scores to compressed indices
    V_idx = [val_to_idx[v] for v in V]
    
    results = []
    last_res = ""
    
    # Process each update and calculate the number of remedial students
    for t, new_idx in zip(T, V_idx):
        p = t - 1  # Student index (0-indexed)
        old_idx = current_scores_idx[p]
        
        # If the student's score has actually changed, update the BIT and recalculate the result
        if old_idx != new_idx:
            # Update BIT: decrement frequency of old score, increment frequency of new score
            curr = old_idx
            while curr <= M:
                bit[curr] -= 1
                curr += curr & (-curr)
            
            curr = new_idx
            while curr <= M:
                bit[curr] += 1
                curr += curr & (-curr)
            
            current_scores_idx[p] = new_idx
            
            # Binary lifting on BIT to find the largest index 'idx' such that prefix_sum(idx) < k.
            # This 'idx' represents the count of students with scores strictly less than the k-th smallest score.
            idx = 0
            current_sum = 0
            for j in bit_len_range:
                next_idx = idx + powers[j]
                if next_idx <= M:
                    val = bit[next_idx]
                    if current_sum + val < k:
                        idx = next_idx
                        current_sum += val
            last_res = str(current_sum)
        else:
            # If the score did not change, the threshold and count remain the same as the previous update.
            # However, if this is the first update, we still need to calculate the initial result.
            if last_res == "":
                idx = 0
                current_sum = 0
                for j in bit_len_range:
                    next_idx = idx + powers[j]
                    if next_idx <= M:
                        val = bit[next_idx]
                        if current_sum + val < k:
                            idx = next_idx
                            current_sum += val
                last_res = str(current_sum)
        
        results.append(last_res)
        
    # Output all results separated by newlines
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。