公式

A - 成績管理システム / Grade Management System 解説 by admin

GPT 5.2 High

Overview

This problem involves managing each student’s score directly in an array, updating and scanning intervals as instructed by queries, and counting “the number of students with scores greater than a reference value.”

Analysis

The operations in this problem are of the following 3 types:

  • Type 1: Two-point update (\(a\) gets \(-v\), \(b\) gets \(+v\))
  • Type 2: Count the number of students in the interval \([l,r]\) whose score is greater than a reference value (the score of student \(x\))
  • Type 3: Add \(+v\) to everyone in the interval \([l,r]\)

At first glance, the combination of “range addition” and “counting elements satisfying a condition within a range” makes you want to consider advanced data structures like segment trees or BITs. However, for Type 2, the “reference value changes every time (and can be any element of the array),” so it cannot be handled like a simple range sum, making it difficult to structure.

The key here is the constraints:

  • \(N \le 5000\)
  • \(Q \le 5000\)

This means at most around \(N \times Q = 25{,}000{,}000\) loop iterations. This is a perfectly feasible amount even in Python, so the approach of straightforwardly maintaining an array and scanning the necessary intervals on the spot is fast enough.

The typical case where a naive approach would TLE is when \(N,Q \le 2\times 10^5\), but since the values in this problem are not that large, this method—which is simpler to implement and less prone to bugs—is actually effective.

Algorithm

Manage scores with score[1..N] (initially 0).

  • Type 1 1 a b v
    Set score[a] -= v, score[b] += v (updating 2 elements).

  • Type 2 2 x l r
    First, get the reference value base = score[x].
    Then iterate through \(i=l..r\), incrementing a counter if score[i] > base.
    Finally, output the counter.

  • Type 3 3 l r v
    For all \(i=l..r\), perform score[i] += v (directly updating the interval).

For example, in Type 2, the reference is “the value of \(score[x]\) at the time of the query,” so the key point is to fix base first and then scan the interval (the reference does not change during the scan).

Complexity

  • Time complexity: \(O(NQ)\) (Types 2 and 3 each have worst-case interval length \(O(N)\), occurring up to \(Q\) times)
  • Space complexity: \(O(N)\) (score array)

Implementation Notes

  • Using 1-indexed (score = [0]*(N+1)) to match student numbers with indices reduces mistakes.

  • Although the input has at most \(Q=5000\), for speed in Python we use sys.stdin.buffer.read() to read all input at once.

  • Scores can become large in absolute value, but Python’s int has arbitrary precision so this is handled naturally.

  • The comparison in Type 2 is “strictly greater than,” so the condition is > (not >=).

    Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)

    score = [0] * (N + 1)
    out = []

    for _ in range(Q):
        t = next(it)
        if t == 1:
            a = next(it)
            b = next(it)
            v = next(it)
            score[a] -= v
            score[b] += v
        elif t == 2:
            x = next(it)
            l = next(it)
            r = next(it)
            base = score[x]
            cnt = 0
            s = score
            for i in range(l, r + 1):
                if s[i] > base:
                    cnt += 1
            out.append(str(cnt))
        else:  # t == 3
            l = next(it)
            r = next(it)
            v = next(it)
            s = score
            for i in range(l, r + 1):
                s[i] += v

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

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.