A - Grade Management System Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は、ある学校の N 人の生徒のスコアを管理するシステムを運営しています。生徒には 1 から N までの番号が付けられており、各生徒のスコアは初め 0 です。

高橋君のもとには Q 個のクエリが時系列順にやってきます。各クエリは以下の 3 種類のいずれかです。

  • 種類 1:スコアの移動 — 生徒 a のスコアを v だけ減らし、生徒 b のスコアを v だけ増やします。ここで a \neq b であり、v は正の整数です。この操作はスコアの現在の値によらず常に行われ、結果としてスコアが負の値になることもあります。
  • 種類 2:スコアの比較に関する問い合わせ — クエリ処理時点での生徒 x のスコアを基準値とします。生徒番号 l 以上 r 以下の生徒のうち、スコアがこの基準値より真に大きい(基準値と等しい場合は含まない)生徒の人数を求めます。生徒 x は区間 [l, r] に含まれるとは限りません。
  • 種類 3:一斉加点 — 生徒番号 l 以上 r 以下のすべての生徒のスコアに正の整数 v を加算します。

各「種類 2」のクエリについて、条件を満たす生徒の人数を出力してください。

制約

  • 1 \leq N \leq 5000
  • 1 \leq Q \leq 5000
  • 種類 1 のクエリにおいて、1 \leq a \leq N, 1 \leq b \leq N, a \neq b, 1 \leq v \leq 10^9
  • 種類 2 のクエリにおいて、1 \leq x \leq N, 1 \leq l \leq r \leq N
  • 種類 3 のクエリにおいて、1 \leq l \leq r \leq N, 1 \leq v \leq 10^9
  • 入力はすべて整数である
  • 入力で与えられる操作の過程で、各生徒のスコアの絶対値は 10^{13} を超えないことが保証される

入力

入力は以下の形式で標準入力から与えられます。

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

1 行目には、生徒の人数 N とクエリの個数 Q がスペース区切りで与えられます。

続く Q 行のそれぞれに、クエリの情報が以下のいずれかの形式で与えられます。

  • 種類 1 の場合: 1 a b v — 生徒 a のスコアを v だけ減らし、生徒 b のスコアを v だけ増やします。a, b は生徒番号、v は移動するスコアの量(正の整数)です。a \neq b が保証されます。
  • 種類 2 の場合: 2 x l r — 生徒 x のスコアを基準値とし、生徒番号 l 以上 r 以下の生徒のうち、スコアが基準値より真に大きい生徒の人数を求めます。x は基準となる生徒の番号、l, r は問い合わせ対象の生徒番号の範囲です。注意:種類 3 とは引数の並び順が異なります。
  • 種類 3 の場合: 3 l r v — 生徒番号 l 以上 r 以下のすべての生徒のスコアに v を加算します。l, r は対象の生徒番号の範囲、v は加算するスコアの量(正の整数)です。

出力

種類 2 のクエリそれぞれについて、条件を満たす生徒の人数を 1 行に 1 つずつ、クエリが与えられた順に出力してください。


入力例 1

3 5
1 1 2 10
2 3 1 3
3 1 2 5
2 1 1 3
2 2 2 3

出力例 1

1
2
0

入力例 2

4 4
1 1 3 5
1 2 4 3
2 4 1 4
2 2 1 4

出力例 2

1
2

入力例 3

5 8
3 2 4 100
1 3 5 50
2 1 1 5
1 2 1 100
3 1 3 10
2 4 1 5
2 3 3 5
2 5 1 5

出力例 3

4
1
1
3

入力例 4

10 12
1 1 5 1000000000
3 1 10 500000000
1 7 3 200000000
2 5 1 10
3 6 10 300000000
1 4 8 100000000
2 1 1 10
2 10 5 9
1 2 9 999999999
3 1 5 100000000
2 3 1 10
2 9 1 10

出力例 4

0
9
2
3
0

入力例 5

1 1
2 1 1 1

出力例 5

0

Score : 266 pts

Problem Statement

Takahashi operates a system that manages the scores of N students at a certain school. The students are numbered from 1 to N, and each student's score is initially 0.

Takahashi receives Q queries in chronological order. Each query is one of the following 3 types:

  • Type 1: Score Transfer — Decrease student a's score by v and increase student b's score by v. Here a \neq b and v is a positive integer. This operation is always performed regardless of the current score values, and scores may become negative as a result.
  • Type 2: Score Comparison Query — Let the score of student x at the time of processing this query be the reference value. Among all students with student numbers from l to r (inclusive), find the number of students whose score is strictly greater than the reference value (students with scores equal to the reference value are not counted). Student x is not necessarily within the range [l, r].
  • Type 3: Batch Score Addition — Add a positive integer v to the scores of all students with student numbers from l to r (inclusive).

For each Type 2 query, output the number of students satisfying the condition.

Constraints

  • 1 \leq N \leq 5000
  • 1 \leq Q \leq 5000
  • For Type 1 queries: 1 \leq a \leq N, 1 \leq b \leq N, a \neq b, 1 \leq v \leq 10^9
  • For Type 2 queries: 1 \leq x \leq N, 1 \leq l \leq r \leq N
  • For Type 3 queries: 1 \leq l \leq r \leq N, 1 \leq v \leq 10^9
  • All input values are integers
  • It is guaranteed that during the course of the operations given in the input, the absolute value of each student's score does not exceed 10^{13}

Input

Input is given from standard input in the following format:

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

The first line contains the number of students N and the number of queries Q, separated by a space.

Each of the following Q lines contains query information in one of the following formats:

  • For Type 1: 1 a b v — Decrease student a's score by v and increase student b's score by v. a and b are student numbers, and v is the amount of score to transfer (a positive integer). It is guaranteed that a \neq b.
  • For Type 2: 2 x l r — Using student x's score as the reference value, find the number of students with student numbers from l to r (inclusive) whose score is strictly greater than the reference value. x is the student number used as the reference, and l, r define the range of student numbers to query. Note: The order of arguments differs from Type 3.
  • For Type 3: 3 l r v — Add v to the scores of all students with student numbers from l to r (inclusive). l and r define the range of target student numbers, and v is the amount of score to add (a positive integer).

Output

For each Type 2 query, output the number of students satisfying the condition, one per line, in the order the queries are given.


Sample Input 1

3 5
1 1 2 10
2 3 1 3
3 1 2 5
2 1 1 3
2 2 2 3

Sample Output 1

1
2
0

Sample Input 2

4 4
1 1 3 5
1 2 4 3
2 4 1 4
2 2 1 4

Sample Output 2

1
2

Sample Input 3

5 8
3 2 4 100
1 3 5 50
2 1 1 5
1 2 1 100
3 1 3 10
2 4 1 5
2 3 3 5
2 5 1 5

Sample Output 3

4
1
1
3

Sample Input 4

10 12
1 1 5 1000000000
3 1 10 500000000
1 7 3 200000000
2 5 1 10
3 6 10 300000000
1 4 8 100000000
2 1 1 10
2 10 5 9
1 2 9 999999999
3 1 5 100000000
2 3 1 10
2 9 1 10

Sample Output 4

0
9
2
3
0

Sample Input 5

1 1
2 1 1 1

Sample Output 5

0