/
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