/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
Paken 王国には N 校の学校があり、 1, 2, \ldots, N の番号が付けられています。学校 i には最初、 A_i 人の生徒が所属しています。もちろん学校である以上、同じ人が永遠に学校に所属し続けることはできません。生徒の人数は途中で変わることがあります。
Paken 王国では毎日のように王国主催の大会が開催されており、それぞれの大会では、招待する学校の候補を表す整数組 (l, r) を定め、学校 l, l+1, \ldots, r のうちから 1 校のみを選び、その学校の生徒を全員招待することになっています。
さて、大会では頭を使うため、糖分補給用に参加者にお菓子が配られます。しかし、このお菓子の個数には次のような条件があります。
- 人によってお菓子の個数が変わらないように、学校 l, l+1, \ldots, r のどの学校に対しても、その学校の生徒の人数が用意するお菓子の個数の約数になるようにする。
- Paken 王国にはあまりお金がないため、用意するお菓子の個数は、上の条件を満たす中で最小になるようにする。
あなたは Paken 王国で唯一のお菓子の会社の社長です。すべての大会のお菓子はあなたの会社に発注されます。あなたは会社の PR のため、どの学校が大会に招待される候補になっているのかを知りたくなりました。 そこで、それぞれの大会について、発注されたお菓子の個数から、その大会で定められた整数組 (l, r) としてあり得るものの個数を求めることにしました。
Paken 王国で起こる出来事は 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