Overview

This problem requires dynamically updating students’ scores while computing the number of students “below the threshold” each time. The threshold is the median (the \(\lceil N/2 \rceil\)-th value) when the scores are sorted.

Analysis

• Since score updates can occur up to \(2 \times 10^5\) times, sorting all scores each time to find the median would result in a time complexity of \(O(Q \cdot N \log N)\), which causes TLE.
• The range of scores is too large for simple array-based counting, but if we can efficiently manage and query “frequencies,” we can also determine the median.
• Therefore, using a Binary Indexed Tree (BIT) as the data structure to manage the occurrence count of each score is effective.
• Additionally, we apply coordinate compression to handle cases where the number of distinct score values is very large.
• By performing binary search on the BIT, we can efficiently find the current median (the \(\lceil N/2 \rceil\)-th element).
• Finally, we obtain the answer by using the BIT’s prefix sum to count the number of students whose scores are strictly less than that median.

Algorithm

Overall Flow:

1. Preprocessing:
   • Collect all initial scores and updated scores, and perform coordinate compression.
   • Create a mapping from score → compressed index.
2. BIT Initialization:
   • Prepare a BIT that manages the occurrence count of each score.
   • Insert the initial scores into the BIT (+1 at the index corresponding to each score).
3. For each update query, process the following:
   • Remove the old score of the target student from the BIT (-1), and insert the new score (+1).
   • Using prefix sums on the BIT, identify the score at the median position via binary search.
     • Specifically, find the “smallest index where the prefix sum is at least \(\lceil N/2 \rceil\).”
   • That score becomes the threshold, so retrieve the count of scores strictly less than it using the BIT’s prefix sum.
   • Record the result.

Example:

For instance, if \(N=5\) and the scores are [10, 20, 30, 40, 50], the median is the 3rd value, which is 30. If an update changes the scores to [10, 20, 25, 40, 50], the median becomes 25, and the students needing extra lessons are 10 and 20, totaling 2 students.

Complexity

• Time complexity: \(O((N + Q) \log N + Q \log Q)\)
  • Coordinate compression: \(O((N + Q) \log Q)\)
  • BIT operations (add/sum): \(O(\log N)\) each
  • Binary search per query: \(O(\log N)\)
• Space complexity: \(O(N + Q)\)
  • Arrays for the BIT and compressed score management

Implementation Notes

• Note that BIT must be handled with 1-indexing.

• Since BIT operations use coordinate-compressed values, a conversion from score → index is required.

• The median position can be computed as \(\lceil N/2 \rceil = (N + 1) // 2\) (using Python’s integer division).

• To find the “k-th smallest value” on the BIT, use binary search to find the smallest i satisfying sum(i) >= k.

• Students needing extra lessons are those “below the threshold,” so identify the boundary using something like bisect_left and count using the BIT’s prefix sum.

  Source Code

import sys
from bisect import bisect_left, bisect_right, insort
import math

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    S = list(map(int, data[idx:idx+N])); idx += N
    queries = []
    for _ in range(Q):
        t = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        queries.append((t-1, v))  # 0-indexed

    # 座標圧縮の準備
    all_values = set(S)
    for _, v in queries:
        all_values.add(v)
    sorted_values = sorted(all_values)
    value_to_idx = {v: i for i, v in enumerate(sorted_values)}
    max_idx = len(sorted_values)

    # 各値の出現回数を管理するBIT (1-indexed)
    class BIT:
        def __init__(self, size):
            self.size = size
            self.tree = [0] * (size + 1)
        
        def add(self, i, delta):
            while i <= self.size:
                self.tree[i] += delta
                i += i & -i
        
        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

    bit = BIT(max_idx)
    scores = S[:]

    # 初期状態でBITに挿入
    for s in scores:
        bit.add(value_to_idx[s] + 1, 1)  # BITは1-indexed

    results = []

    for t, v in queries:
        old_val = scores[t]
        old_idx = value_to_idx[old_val]
        new_idx = value_to_idx[v]
        
        # 古い値を削除
        bit.add(old_idx + 1, -1)
        # 新しい値を追加
        bit.add(new_idx + 1, 1)
        scores[t] = v

        # 中央値のインデックスを計算 (1-based)
        mid_pos = (N + 1) // 2  # ceil(N/2) = (N+1)//2 for integer division in Python when N>=1

        # BIT上でmid_pos番目の要素を探す (二分探索)
        # つまり、sum(x) >= mid_pos となる最小のxを見つける
        left_b = 1
        right_b = max_idx
        median_idx = right_b
        while left_b <= right_b:
            mid = (left_b + right_b) // 2
            if bit.sum(mid) >= mid_pos:
                median_idx = mid
                right_b = mid - 1
            else:
                left_b = mid + 1

        # 基準値はsorted_values[median_idx - 1] (0-indexed)
        threshold = sorted_values[median_idx - 1]

        # 厳密にthreshold未満の要素の個数を求める
        # それはvalue_to_idx[threshold]より前のインデックスの和
        pos = bisect_left(sorted_values, threshold)
        if pos == 0:
            count = 0
        else:
            count = bit.sum(pos)
        
        results.append(count)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.