配点 : 700 点
問題文
在帕肯王国 N 有一所学校 它的编号为 1, 2, \ldots, N 。学校 i 最初有 A_i 学生属于这个群体。当然,既然是学校,同一个人不可能永远继续属于学校。课程期间学生人数可能会发生变化。
在帕肯王国,王国主办的锦标赛几乎每天都会举行,而每次锦标赛中都会使用一组代表要邀请的候选学校的整数。 (l, r) 和学校 l, l+1, \ldots, r 您将仅选择一所学校并邀请该学校的所有学生。
比赛时,会给参赛者发放糖果,补充糖份摄入量,以便开动大脑。但是,糖果的数量适用以下条件:
- 学校正在努力防止糖果的数量因人而异。 l, l+1, \ldots, r 对于任何学校,该学校的学生人数应该是准备的糖果数量的除数。
- 帕肯王国没有多少钱,所以准备的糖果数量应该是满足上述条件的最少数量。
你是帕肯王国唯一一家糖果公司的总裁。所有比赛糖果都将从贵公司订购。出于贵公司的公关目的,您想知道哪些学校有资格受邀参加比赛。 因此,对于每个锦标赛,我们将根据订购的糖果数量计算由该锦标赛确定的整数集。 我决定找到可能的 (l, r) 的数量。
帕肯王国发生的事情是 有 Q 事件,每个事件都由以下形式之一的查询表示:
- 入学查询
1 k a: 学校 k 里有人 a 人们注册。学校 属于 k 的学生 a 人数将会增加。 - 毕业查询
来自
2 k b: 学校 k 的人 b 人们毕业了。学校 k 的学生 b 人少了。 - 赛事查询
3 s:在某场比赛中,发放了糖果。 s 件已订购。您是一组整数,代表可能被邀请参加比赛的学校。 找出可能的 (l, r) 的数量。 当
Q 事件按顺序发生时,查找每个竞赛查询的答案。
请注意,学校只是一所学校,因此属于任何学校的学生人数始终相同。 1 以上 10^9 保证:
制約
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq A_j \leq 10^9 (1 \leq j \leq N)
- 关于入学查询和毕业查询, 1 \leq k \leq N
- 关于入学查询, 1 \leq a \leq 10^9
- 关于毕业查询, 1 \leq b \leq 10^9
- 关于锦标赛查询, 1 \leq s \leq 10^9
- 在任何给定时间,对于每所学校,属于该学校的学生人数为 1 以上 10^9 小于或等于
- 所有输入均为整数
小課題
- (150 点) N, Q \leq 10^3
- (200 分)不给出录取和毕业查询。
- (200 点)在任何时间点,对于每所学校,属于该学校的学生 10 不到一个人
- (150 点)无附加约束
入力
输入是按以下格式从标准输入给出的。
N Q
A_1 A_2 \ldots A_N
\mathrm{query}1
\mathrm{query}2
\vdots
\mathrm{query}Q
i 第查询 \mathrm{query}i 以表示查询类型的整数开头。 给出 c_i (1, 2, 3 )。 当
c_i = 1 时,附加一个整数 另外给出了 k 和 在 a 。
c_i = 2 时,附加一个整数 另外给出了 k 和 在 b 。
c_i = 3 时,附加一个整数 另外给出了 s 。
也就是说,每个查询是 3 可以采用以下两种格式之一: 满足
1 k a
2 k b
3 s
出力
c_i = 3 的查询数量为 q 作为 在 q 行输出。 由于字符串以 j (1 \leq j \leq q) 行中,在此类查询中 打印第 j 个答案。
入力例 1
4 3 1 2 3 4 3 12 1 1 3 3 12
出力例 1
3 4
每个查询的结果应如下所示:
- 赛事查询。 (l, r) = (1, 4), (2, 4), (3, 4) 满足条件。
- 招生查询。学校 1 的学生 3 各学校在校学生人数为 它变成 4, 2, 3, 4 。 满足
- 赛事查询。 (l, r) = (1, 3), (1, 4), (2, 4), (3, 4) 满足条件。
此输入示例是一个小作业。 1, 3, 4 约束。
入力例 2
10 5 10 1 8 3 10 10 6 3 3 7 3 30 3 7 3 4 3 10 3 1
出力例 2
11 1 0 5 1
此示例输入满足所有子任务约束。
入力例 3
20 20 13 5 30 10 15 22 30 4 11 18 10 23 9 1 27 8 5 6 16 26 3 60 3 90 2 19 11 2 7 6 2 5 6 3 12870 3 198 1 12 3 2 10 1 3 30 3 5 2 18 5 3 234 3 291720 1 10 6 3 1776060 3 198 3 10 3 792 3 30
出力例 3
1 1 1 2 7 3 2 2 1 1 2 3 4
此输入示例是一个小作业。 1, 4 约束。
原案: shiomusubi496 对于