分数: 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