Overview

Given \(N\) students whose scores are updated \(Q\) times, after each update we need to find the \(\lceil N/2 \rceil\)-th value (the baseline) in the sorted sequence, and answer how many students have scores strictly less than this baseline.

Analysis

Problem Setup

First, let’s confirm the definition of the baseline. When the scores of \(N\) students are sorted in ascending order, the \(\lceil N/2 \rceil\)-th value is the baseline. For example:

• When \(N = 5\): \(\lceil 5/2 \rceil = 3\) → the 3rd smallest
• When \(N = 4\): \(\lceil 4/2 \rceil = 2\) → the 2nd smallest

Students eligible for supplementary lessons are those whose scores are strictly less than the baseline (students with scores equal to the baseline are not eligible).

Naive Approach and Its Issues

If we re-sort all scores after every update, each sort takes \(O(N \log N)\), resulting in \(O(QN \log N)\) over \(Q\) queries. When \(N, Q\) can be up to \(2 \times 10^5\), this is too slow.

Idea for Optimization

If we can maintain the set of scores in a sorted state at all times, then deletion, insertion, k-th element retrieval, and counting elements less than a given value can all be done efficiently. This requires a data structure equivalent to a balanced binary search tree.

In Python, the SortedList from the sortedcontainers library provides exactly this, with each operation running in \(O(\log N)\).

Algorithm

1. Initialization: Add all students’ scores to a SortedList. Maintain each student’s current score in an array \(S\).
2. Precompute \(k = \lceil N/2 \rceil\).
3. For each update \((T_j, V_j)\):
   • Remove student \(T_j\)’s old score from the SortedList.
   • Add the new score \(V_j\) to the SortedList.
   • Update \(S[T_j]\) to \(V_j\).
   • The \((k-1)\)-th element (0-indexed) of the SortedList is the baseline.
   • Use bisect_left(baseline) to find the number of elements less than the baseline. This is the number of students eligible for supplementary lessons.

Concrete Example

For \(N=5\), scores \([50, 30, 70, 20, 60]\): - Sorted sequence: \([20, 30, 50, 60, 70]\) - \(k = 3\), so the baseline is \(50\) (index \([2]\) in 0-indexed) - Elements less than \(50\): \(20, 30\), which is \(2\) → \(2\) students need supplementary lessons

Now if student 3’s score changes from \(70 \to 40\): - Sorted sequence: \([20, 30, 40, 50, 60]\) - The baseline is \(40\) - Elements less than \(40\): \(20, 30\), which is \(2\) → \(2\) students need supplementary lessons

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Initialization involves \(N\) insertions (each \(O(\log N)\)), and each query involves deletion, insertion, index access, and binary search, each \(O(\log N)\)
• Space complexity: \(O(N)\)
  • For storing the SortedList and the score array

Implementation Notes

• 0-indexed vs 1-indexed conversion: \(k = \lceil N/2 \rceil\) is 1-indexed, so access the SortedList with sl[k-1].

• Tracking old scores: Since the old score must be removed from the SortedList during updates, always keep each student’s current score recorded in array \(S\).

• Using bisect_left: sl.bisect_left(baseline) returns the number of elements less than baseline (elements equal to baseline are not included). This directly gives the number of students eligible for supplementary lessons.

• Fast I/O: Since \(N, Q\) can be large, read all input at once with sys.stdin.buffer.read(), and write all output at once with '\n'.join().

  Source Code

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()

---

This editorial was generated by claude4.6opus-thinking.