Overview

In this problem, we need to simulate a system that performs three types of operations on student scores (score transfer, score comparison within a range, and batch score addition to a range), and answer queries that ask for the number of students satisfying specified conditions.

Analysis

This problem involves the following three operations:

1. Type 1 (Score Transfer): Subtract \(v\) points from student \(a\) and add \(v\) points to student \(b\).
2. Type 2 (Score Comparison Query): Find the number of students in the interval \([l, r]\) whose scores are strictly greater than the score of student \(x\).
3. Type 3 (Range Addition): Add \(v\) points to the scores of all students in the interval \([l, r]\).

What about a naive approach?

The simplest method is to simulate all operations directly using an array. For example, prepare an array scores to hold the students’ scores, update elements for Type 1 and Type 3 operations, and for Type 2 queries, check each score in the interval one by one.

However, with this approach, in the worst case:

• Type 2 queries scan the entire interval (up to \(N\)) → \(O(N)\)
• Type 3 queries also update the entire interval → \(O(N)\)

Since the number of queries \(Q\) is at most 5000, the worst-case complexity is \(O(Q \cdot N) = 2.5 \times 10^7\), which is not sufficiently fast.

Improvement

However, the constraints \(N, Q \leq 5000\) are very lenient. This means that even with somewhat heavy constant factors, processing each query in linear time \(O(N)\) is fast enough.

Therefore, simple array-based management works sufficiently fast as follows:

• Manage each student’s score in a list scores (1-indexed)
• Directly update scores for Type 1 and Type 3 operations
• For Type 2 queries, check scores in the interval \([l, r]\) one by one and count

Additionally, while Type 3 (Range Addition) loops through the interval each time for updates, which is inefficient, it still fits within the time limit due to the small constraints.

Algorithm

This solution processes operations with the following steps:

1. Prepare an array scores to hold student scores (initialized to 0)
2. Process each query sequentially:
   • Type 1: scores[a] -= v, scores[b] += v
   • Type 2: Using scores[x] as the reference, count the number of students in the interval [l, r] with a score greater than that value
   • Type 3: Add v to all scores[i] in the interval [l, r]
3. Output the results of Type 2 queries in order

This method performs interval operations naively, but it is sufficiently fast given the small constraints.

Complexity

• Time complexity: \(O(Q \cdot N)\)
• Space complexity: \(O(N)\)

※In practice, \(Q \cdot N \leq 2.5 \times 10^7\), which can be processed within a few seconds on modern CPUs.

Implementation Notes

• Using 1-indexed student scores makes it easier to align with the input.

• For Type 2 queries, note that we count only scores that are strictly greater; equal scores are not counted.

• The addition in Type 3 is also performed naively with a loop, but there are no speed issues.

• sys.stdin.read is used for fast input reading.

  Source Code

import sys
from bisect import bisect_left, bisect_right

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def add(self, i, delta):
        while i <= self.n:
            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

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
    
    # 座標圧縮の準備
    values = set()
    queries = []
    scores = [0] * (N + 1)  # 1-indexed
    adds = [0] * (N + 1)    # 遅延加算用
    
    for _ in range(Q):
        t = int(data[idx])
        idx += 1
        if t == 1:
            a = int(data[idx])
            idx += 1
            b = int(data[idx])
            idx += 1
            v = int(data[idx])
            idx += 1
            queries.append((1, a, b, v))
            values.add(-v)
            values.add(v)
        elif t == 2:
            x = int(data[idx])
            idx += 1
            l = int(data[idx])
            idx += 1
            r = int(data[idx])
            idx += 1
            queries.append((2, x, l, r))
            values.add(0)
        else:
            l = int(data[idx])
            idx += 1
            r = int(data[idx])
            idx += 1
            v = int(data[idx])
            idx += 1
            queries.append((3, l, r, v))
            values.add(v)
            values.add(-v)
    
    # スコアの初期値も考慮に入れる（0）
    values.add(0)
    sorted_values = sorted(values)
    value_to_idx = {v: i+1 for i, v in enumerate(sorted_values)}
    M = len(sorted_values)
    
    # BITの準備 (生徒番号ごとにBITを持つのは非効率なので、座標圧縮＋区間加算BIT or 平方分割などの工夫が必要だが、制約的に可能)
    # しかし、Pythonでの高速化が難しいので、安全策として、生徒のスコアを直接管理し、種類2クエリではナイーブに処理する
    
    # 制約がN,Q<=5000なので、毎回の種類2クエリでO(N)しても間に合う
    # 種類3は遅延加算で対応
    
    # 遅延伝播用のデータ構造
    lazy = [0] * (N + 1)
    
    results = []
    
    for query in queries:
        if query[0] == 1:
            _, a, b, v = query
            scores[a] -= v
            scores[b] += v
        elif query[0] == 2:
            _, x, l, r = query
            base = scores[x]
            count = 0
            for i in range(l, r+1):
                if scores[i] > base:
                    count += 1
            results.append(count)
        else:
            _, l, r, v = query
            for i in range(l, r+1):
                scores[i] += v
                
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

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