[ARC017D] ARCたんクッキー

## 题目描述 给定一个长度为$N$的序列$A$，要求维护两种操作： - 将一个区间里的数加上$x$ - 问一个区间里的所有数的最大公约数 ### 输入格式 第一行一个正整数$N$，代表序列长度 第二行$N$个正整数，代表序列$A$ 第三行一个正整数$M$，代表操作次数 接下来有$M$行，每行三个整数$op,L,R$ - 如果$op=0$，那么要求输出$[L,R]$之间的所有数的最大公约数 - 如果$op\ne 0$，那么将$[L,R]$里的所有数加上$op$ ### 输出格式 对每个查询操作，输出一行一个正整数，代表区间里的最大公约数 ## 说明&提示 ### 数据范围 $1\le N,M\le 100000,1\le op,A_i\le 10^9$ 有$30\%$数据点满足每次只修改一个数 ### 样例1解释 - `A=[6,3,38,49]` - `Output gcd(6,3,38)=1` - `A->[6,3,36,49]` - `Output gcd(6,3,36)=3` - `A->[6,12,36,49]` - `Output gcd(6,12)=6` - `A->[6,12,42,49]` - `Output gcd(42,49)=7`

[problemUrl]: https://atcoder.jp/contests/arc017/tasks/arc017_4 私はとあるクッキー工場に勤めている。 この工場では「ARCたんクッキー」というかわいいクッキーを作っている。 この工場には $ N $ 個のARCたんクッキー製造機があり、製造機には $ 1 $ から $ N $ まで番号がついている。製造機ごとに異なるフレーバーが設定されているため、異なる製造機から作られたクッキー同士は区別される。また製造機ごとに一度に生成するクッキーの量が設定されている。製造機は指定された製造数のクッキーを一度に全て生成する。 この度、私が勤めている工場では、$ M $ 日間、工場見学ツアーを実施することになった。それぞれの日には次のいずれかの作業が実行される。 - 見学ツアーを実施する。ツアーではそれぞれの日ごとに定められた、ある連続した番号の製造機をちょうど $ 1 $ 回ずつ稼働させ、それらの製造機が生成したクッキー全てをお土産としてツアー参加者に配る予定である。 - メンテナンスを実施し、それぞれの日ごとに定められた、ある連続した番号の製造機の製造数を一定数増減させる。 工場はとても広く迷子になりやすいので、それぞれのツアー実施日内ではツアー客の定員を固定することになっている。 ここの工場長は割り切れないことを好まず、どの製造機から作られたクッキーもその日参加した全てのツアー客に同数ずつ配らなければ気が済まない。また、ARCたんクッキーの一部を配らない、砕くなどかわいそうなことはしてはならない。つまり、作ったクッキーは全てツアー客に平等に配らなければならない。一方でこの工場の宣伝のため、このような条件を満たしつつできるだけ多くのツアー客を受け入れたいと考えている。 立案者である私は、それぞれのツアー実施日において、$ 1 $ 回あたりのツアーに参加できるツアー客の最大値を求めることになった。しかしながら私は新しいフレーバー開発に忙しい。そこであなたに是非ともこの問題を解いてもらいたい。 入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ a_2 $ … $ a_N $ $ M $ $ t_1 $ $ l_1 $ $ r_1 $ $ t_2 $ $ l_2 $ $ r_2 $ : $ t_M $ $ l_M $ $ r_M $ 1. $ 1 $ 行目には製造機の個数を表す整数 $ N\ (1≦N≦100,000) $ が与えられる。 2. $ 2 $ 行目には $ N $ 個の整数が空白を区切りとして与えられる。 - 整数 $ a_i\ (1≦a_i≦10^9) $ は製造機 $ i\ (1≦i≦N) $ が初期状態で製造するクッキーの個数を表す。 13. $ 3 $ 行目にはツアー及びメンテナンスをする日数を表す整数 $ M\ (1≦M≦100,000) $ が与えられる。 14. $ 4 $ 行目から $ M $ 回、ツアー及びメンテナンスの工程を表す $ 3 $ つの整数が空白を区切りとして与えられる。 - 整数 $ t_i\ (-10^9＜t_i＜10^9) $ は通算 $ i\ (1≦i≦M) $ 日目にする作業を表す。 - $ t_i=0 $ ならその日はツアーを実施する日であること表す。 - $ t_i≠0 $ ならその日はメンテナンスを実施する日であること表す。 - 少なくとも $ 1 $ 回はツアーを実施する日がある。 - 整数 $ l_i,r_i\ (1≦l_i≦r_i≦N) $ は通算 $ i $ 日目にする作業の詳細に関する情報を表す。 - その日がツアーを実施する日なら、番号 $ l_i\ ,\ l_i+1,\ ...\ ,\ r_i $ の製造機をツアー実施時に使用することを表す。 - その日がメンテナンスを実施する日なら、番号 $ l_i\ ,\ l_i+1,\ ...\ ,\ r_i $ の製造機に対し、メンテナンスを実施することを表す。$ t_i $ が正ならそれぞれの製造機の製造数を $ t_i $ ずつ増やし、$ t_i $ が負なら製造数を $ -t_i $ ずつ減らす処理をメンテナンス時に行う。 - 全てのメンテナンスを実施する日において、メンテナンス実施後、どの製造機も製造するクッキーの枚数が $ 1 $ 枚以上 $ 10^9 $ 枚以下である。 この問題には部分点が設定されている。 - 下記の条件を満たすテストケースのみで構成された、$ 30 $ 点分のセットがある。 - 全ての整数 $ i\ (1≦i≦M) $ において、$ t_i≠0 $ なら $ l_i=r_i $ が成立する。 - 上記のセットを含む全てのテストケースに正解することで、残りの $ 70 $ 点を得られる。 ツアーを行う回数を $ T $ とする。このとき出力は $ T $ 行だけ出力せよ。$ i $ 行目には、初日から数えて $ i $ 回目のツアー実施日において、観光客を呼べる人数の最大値を出力せよ。 なお、出力の最後には改行を入れること。 ``` <pre class="prettyprint linenums"> 4 6 3 38 49 7 0 1 3 -2 3 3 0 1 3 9 2 2 0 1 2 6 3 3 0 3 4 ``` ``` <pre class="prettyprint linenums"> 1 3 6 7 ``` - 初期状態における製造機ごとのクッキー製造数は、$ 1 $ 番の製造機から順に $ 6,3,38,49 $ となっている。 - $ 1 $ 日目はツアーを実施する。 - ツアーでは製造機 $ 1,2,3 $ を用いるので、製造されるクッキーの個数は順に $ 6,3,38 $ となる。 - この場合、観光客は $ 1 $ 人しか受け入れられない。 - $ 2 $ 日目はメンテナンスを実施する。 - 製造機 $ 3 $ の製造数を $ 2 $ だけ減らす。メンテナンス後のクッキー製造数は、$ 1 $ 番の製造機から順に $ 6,3,36,49 $ となる。 - $ 3 $ 日目はツアーを実施する。 - ツアーでは製造機 $ 1,2,3 $ を用いるので、製造されるクッキーの個数は順に $ 6,3,36 $ となる。 - この場合、観光客は最大で $ 3 $ 人受け入れられる。 - $ 4 $ 日目はメンテナンスを実施する。 - 製造機 $ 2 $ の製造数を $ 9 $ だけ増やす。メンテナンス後のクッキー製造数は、$ 1 $ 番の製造機から順に $ 6,12,36,49 $ となる。 - $ 5 $ 日目はツアーを実施する。 - ツアーでは製造機 $ 1,2 $ を用いるので、製造されるクッキーの個数は順に $ 6,12 $ となる。 - この場合、観光客は最大で $ 6 $ 人受け入れられる。 - $ 6 $ 日目はメンテナンスを実施する。 - 製造機 $ 3 $ の製造数を $ 6 $ だけ増やす。メンテナンス後のクッキー製造数は、$ 1 $ 番の製造機から順に $ 6,12,42,49 $ となる。 - $ 7 $ 日目はツアーを実施する。 - ツアーでは製造機 $ 3,4 $ を用いるので、製造されるクッキーの個数は順に $ 42,49 $ となる。 - この場合、観光客は最大で $ 7 $ 人受け入れられる。 ``` <pre class="prettyprint linenums"> 3 1 3 17 6 16 1 1 8 2 2 0 1 2 0 2 2 6 2 2 0 1 3 ``` ``` <pre class="prettyprint linenums"> 1 11 17 ```