← 返回题目列表

AtCoder · awc0067_a

A. 等级管理系统

中文机器翻译题面 查看原题

分数: 266 分

问题陈述

高桥运营着一个管理分数的系统 N 某学校的学生。学生编号从 1 to N,每个学生的分数最初是 0.

高桥收到 Q 按时间顺序查询。每个查询都是以下之一 3 类型:

  • 类型 1:分数转移 — 减少学生 a的得分为 v 并增加学生 b的得分为 v。这里 a \neq b 和 v 是正整数。无论当前分数值如何,始终执行此操作,结果分数可能会变为负值。
  • 类型2:分数比较查询 — 让学生的分数 x 是处理该查询时的参考值。在所有学生中,学生人数为 l to r (含),查找成绩为的学生人数 严格大于 参考值(成绩等于参考值的学生不计算在内)。学生 x 不一定在范围内 [l, r].
  • 类型3:批量分数相加 — 添加一个正整数 v 为学生编号为 的所有学生的分数 l to r (含)。

对于每个类型 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

第一行包含学生人数 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 to r (含)其分数严格大于参考值。 x 是用作参考的学号,并且 l, r 定义要查询的学号范围。 注意:参数的顺序与类型 3 不同。
  • 对于类型 3: 3 l r v — 添加 v 为学生编号为 的所有学生的分数 l to r (含)。 l 和 r 定义目标学生人数的范围,以及 v 是要添加的分数量(正整数)。

输出

对于每个类型 2 查询,按照给出查询的顺序输出满足条件的学生人数,每行一个。


示例输入 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