概要

各更新後の得点集合に対して「小さい方から \(\lceil N/2\rceil\) 番目の点数（基準値）」を求め、その基準値より厳密に小さい人数を毎回出力する問題です。
更新が最大 \(2\times 10^5\) 回あるため、更新のたびに並べ替えるのではなく、データ構造で高速に処理します。

考察

重要な観察

• 基準値は、得点を昇順に並べたときの \(k=\lceil N/2\rceil\) 番目（本問では \(k=(N+1)//2\)）の値です。
• 求めたいのは「基準値そのもの」ではなく、最終的に
  • 基準値より小さい人数（＝昇順で基準値が現れる位置の手前までの個数） を出力すればよい、という点がポイントです。

例えば \(N=5\) のとき \(k=3\) です。得点を並べて
\([10, 20, 20, 50, 80]\) なら基準値は \(A_3=20\)、補習対象は \(20\) 未満の \(2\) 人です。
同点が複数いても「基準値未満」だけ数えればよいので、結局は「\(k\) 番目の値を見つけ、その値未満の個数を数える」問題になります。

素朴解がダメな理由

更新のたびに 1. 全員の得点を配列に集める 2. ソートして \(k\) 番目を取る 3. 未満の個数を数える

をすると、1 回あたり \(O(N\log N)\) で、全体で \(O(QN\log N)\) となり確実に TLE します。

解決方針

• 得点の「値」そのものを直接扱うのではなく、座標圧縮して「小さい順の順位（インデックス）」に変換する。
• 各得点（圧縮後のインデックス）に「その点数の人数」が何人いるかを持ち、更新で増減させる。
• 「\(k\) 番目の要素（順序統計）」を高速に求められるように、個数の累積を管理する。

このために Fenwick Tree（BIT） を使います。

アルゴリズム

1. 座標圧縮（オフライン）

更新後に現れうる得点は、初期得点 \(S_i\) と更新値 \(V_j\) のどちらかです。
よってそれらをすべて集めてソートし、重複を削除して

• 実際の得点 \(x\)
• 圧縮後の位置 \(idx(x)\in[1..M]\)

の対応を作ります（\(M\) は異なる得点の種類数）。

2. Fenwick Tree に「各点数の人数」を入れる

Fenwick Tree には - bit[idx] = その得点（圧縮 idx）の人数

を入れておき、初期得点を全員分 add(idx(S_i), +1) します。

3. 更新処理

\(j\) 回目の更新で、生徒 \(t\) の点数が old -> v に変わるとき

1. add(idx(old), -1)（古い点数の人数を減らす）
2. add(idx(v), +1)（新しい点数の人数を増やす）

4. 基準値（\(k\) 番目）を Fenwick Tree から探す

\(k=\lceil N/2\rceil = (N+1)//2\) とします。

Fenwick Tree の累積和 sum(i) は「圧縮インデックス \(\le i\) の人数」です。
よって「累積人数が初めて \(k\) 以上になる最小の \(i\)」が、\(k\) 番目の要素の位置です。

コードでは kth(k) でこれを 二分探索（BIT の binary lifting） により \(O(\log M)\) で求めています。

5. 出力（基準値未満の人数）

基準値の圧縮位置を th_idx とすると、基準値未満の人数は

• sum(th_idx - 1)

です（基準値と同じ点数の人は含めないため、ひとつ手前までの累積を取ります）。

計算量

• 時間計算量:
  
  • 座標圧縮: \(O((N+Q)\log(N+Q))\)
    
  • 各更新: Fenwick の更新 2 回 + \(k\) 番目検索 + 累積和で \(O(\log M)\)
    
  • 合計: \(O((N+Q)\log(N+Q))\)
• 空間計算量: \(O(N+Q+M)\)（得点配列・クエリ保持・Fenwick・圧縮配列）

実装のポイント

• 座標圧縮は更新値も含めて作る必要があります（途中で初登場する点数があるため）。

• Fenwick Tree は 1-indexed で実装すると扱いやすいです（コードでも comp[v] = i+1）。

• kth(k) は「累積和が \(k\) 以上になる最小位置」を返すように実装します。BIT の内部構造を利用した binary lifting により \(O(\log M)\) で求められます。

• 求めるのは「基準値未満」なので、最後は必ず sum(th_idx - 1) にする点に注意してください。

  ソースコード

import sys

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

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

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

    def kth(self, k):
        idx = 0
        bit = self.bit
        step = 1 << (self.n.bit_length() - 1)
        cur = 0
        while step:
            nxt = idx + step
            if nxt <= self.n and cur + bit[nxt] < k:
                cur += bit[nxt]
                idx = nxt
            step >>= 1
        return idx + 1

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)
    S = [next(it) for _ in range(N)]

    T = [0] * Q
    V = [0] * Q
    all_vals = S[:]
    for j in range(Q):
        t = next(it)
        v = next(it)
        T[j] = t
        V[j] = v
        all_vals.append(v)

    vals = sorted(set(all_vals))
    comp = {v: i + 1 for i, v in enumerate(vals)}  # 1-based
    M = len(vals)

    fw = Fenwick(M)
    for s in S:
        fw.add(comp[s], 1)

    k = (N + 1) // 2
    out_lines = []
    for j in range(Q):
        t = T[j] - 1
        v = V[j]
        old = S[t]
        fw.add(comp[old], -1)
        S[t] = v
        fw.add(comp[v], 1)

        th_idx = fw.kth(k)
        out_lines.append(str(fw.sum(th_idx - 1)))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

---

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