D - ARCたんクッキー 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

私はとあるクッキー工場に勤めている。

この工場では「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) が初期状態で製造するクッキーの個数を表す。
  3. 3 行目にはツアー及びメンテナンスをする日数を表す整数 M (1≦M≦100,000) が与えられる。
  4. 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 回目のツアー実施日において、観光客を呼べる人数の最大値を出力せよ。

なお、出力の最後には改行を入れること。

入力例 1

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

出力例 1

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 人受け入れられる。

入力例 2

3
1 3 17
6
16 1 1
8 2 2
0 1 2
0 2 2
6 2 2
0 1 3

出力例 2

1
11
17
  • このテストケース内の 4 日目のように、ツアー実施日に稼働させる製造機が 1 つだけのこともある。