Overview

After each update, we need to find the “score at position \(\lceil N/2\rceil\) from the smallest (the threshold value)” in the current set of scores, and output the number of people whose scores are strictly less than this threshold each time.
Since there can be up to \(2\times 10^5\) updates, instead of re-sorting after each update, we use a data structure to process this efficiently.

Analysis

Key Observations

• The threshold value is the \(k=\lceil N/2\rceil\)-th value (in this problem, \(k=(N+1)//2\)) when scores are sorted in ascending order.
• The key point is that we don’t need “the threshold value itself” — ultimately, we just need to output:
  • The number of people with scores less than the threshold (= the count of elements before the position where the threshold appears in sorted order).

For example, when \(N=5\), \(k=3\). If the sorted scores are
\([10, 20, 20, 50, 80]\), the threshold is \(A_3=20\), and the number of students needing supplementary lessons is \(2\) (those with scores less than \(20\)).
Even if there are ties at the threshold value, we only need to count those “strictly less than the threshold,” so the problem reduces to “find the \(k\)-th value, then count the number of elements less than that value.”

Why the Naive Approach Fails

If we do the following after each update: 1. Collect all scores into an array 2. Sort and take the \(k\)-th element 3. Count elements less than it

This costs \(O(N\log N)\) per update, giving \(O(QN\log N)\) overall, which will certainly TLE.

Solution Strategy

• Instead of working with the score “values” directly, use coordinate compression to convert them into “ranks (indices) in sorted order.”
• For each score (compressed index), maintain how many people have that score, and increment/decrement during updates.
• To efficiently find “the \(k\)-th element (order statistic),” manage cumulative counts.

For this, we use a Fenwick Tree (BIT).

Algorithm

1. Coordinate Compression (Offline)

The scores that can appear after updates are either initial scores \(S_i\) or update values \(V_j\).
So we collect all of them, sort them, remove duplicates, and create a mapping:

• Actual score \(x\)
• Compressed position \(idx(x)\in[1..M]\)

(\(M\) is the number of distinct score values).

2. Insert “count of each score” into the Fenwick Tree

The Fenwick Tree stores: - bit[idx] = number of people with that score (compressed idx)

We initialize by doing add(idx(S_i), +1) for all students.

3. Update Processing

For the \(j\)-th update, when student \(t\)’s score changes from old -> v:

1. add(idx(old), -1) (decrease the count of the old score)
2. add(idx(v), +1) (increase the count of the new score)

4. Find the Threshold (\(k\)-th element) from the Fenwick Tree

Let \(k=\lceil N/2\rceil = (N+1)//2\).

The prefix sum sum(i) of the Fenwick Tree gives “the number of people with compressed index \(\le i\).”
Therefore, “the smallest \(i\) such that the cumulative count first reaches \(k\) or more” is the position of the \(k\)-th element.

In the code, kth(k) finds this using binary search (binary lifting on the BIT) in \(O(\log M)\).

5. Output (Number of People Below the Threshold)

If the compressed position of the threshold is th_idx, then the number of people with scores less than the threshold is:

• sum(th_idx - 1)

(Since we don’t include people with the same score as the threshold, we take the cumulative sum up to one position before.)

Complexity

• Time complexity:
  
  • Coordinate compression: \(O((N+Q)\log(N+Q))\)
    
  • Each update: 2 Fenwick updates + \(k\)-th element search + prefix sum, all \(O(\log M)\)
    
  • Total: \(O((N+Q)\log(N+Q))\)
• Space complexity: \(O(N+Q+M)\) (score array, query storage, Fenwick Tree, compression array)

Implementation Notes

• Coordinate compression must include update values as well (since scores may appear for the first time mid-process).

• The Fenwick Tree is easier to implement with 1-indexed arrays (in the code, comp[v] = i+1).

• kth(k) should be implemented to return “the smallest position where the prefix sum is at least \(k\).” This can be computed in \(O(\log M)\) using binary lifting that exploits the internal structure of the BIT.

• Since we want “strictly less than the threshold,” make sure to use sum(th_idx - 1) at the end.

  Source Code

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

---

This editorial was generated by gpt-5.2-high.