No.017 D

ツアーの日は各クッキー製造機が製造するクッキー数の最大公約数の人数を呼べる.

最大公約数を計算するセグメントツリーで製造するクッキー数を管理すれば, 部分点をもらえるはずである.

満点をもらうためには以下を使う.

$$\gcd(a_1, a_2, a_3, \dots, a_n) = \gcd(a_1, \vert a_1-a_2 \vert, \vert a_2-a_3 \vert, \dots, a_{n-1}-a_n)$$

$a_i$ はクエリの区間すべての更新が必要なので和を計算する遅延伝播セグメントツリーで管理し, $\vert a_i-a_{i+1} \vert$ は区間の端しか更新が必要ないので最大公約数を計算する普通のセグメントツリーで管理する.