← 返回题目列表

AtCoder · pakencamp_2021_day3_e

E. 糖果

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

配点 : 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 小于或等于
  • 所有输入均为整数

小課題

  1. (150 点) N, Q \leq 10^3
  2. (200 分)不给出录取和毕业查询。
  3. (200 点)在任何时间点,对于每所学校,属于该学校的学生 10 不到一个人
  4. (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

每个查询的结果应如下所示:

  1. 赛事查询。 (l, r) = (1, 4), (2, 4), (3, 4) 满足条件。
  2. 招生查询。学校 1 的学生 3 各学校在校学生人数为 它变成 4, 2, 3, 4 。 满足
  3. 赛事查询。 (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 对于