yukicoder No.749 クエリ全部盛り

問題

すべての要素が0で初期化された長さNの数列{a_i}が与えられる。
Q個のクエリが与えられるので、処理せよ。
各クエリ(q,l,r,k)はqの値に応じた処理を行うこと。

• q=0: k*Σ_{i=l}^r a_iのmod 10^9+7を出力
• q=1: l <= i <= rについて、a_iをkに変更
• q=2: l <= i <= rについて、a_iをa_i+kに変更
• q=3: l <= i <= rについて、a_iをa_i*kに変更
• q=4: l <= i <= rについて、a_iをa_i+k*F_iに変更
  • ただし、F_iはフィボナッチ数列のi番目の値

制約

• 1 <= N <= 10^6
• 0 <= Q <= 10^5
• 0 <= l <= r < N
• 0 <= k <= 10^9

解法

範囲更新として、遅延セグメント木を検討する。
遅延セグメント木を考えるため、モノイドMと作用素Opの構造、それらの写像、単位元を考える。

まず、モノイドMについて必要そうな構造を考える。
query処理で必要なのはq=0の時で、Σa_iが必要。また、q=4で、iについてのF_i値がそれぞれ個別に必要となる。
ここで、{a_i, F_i}という元を考える。
二項演算●は、和が欲しいので、{a_i, F_i}●{a_j, F_j}={a_i+a_j, F_i+F_j}で考える。
(F_i部分も、結局k倍したものの和が欲しいので、和のk倍から求めるのに和の形にしておく)
単位元は{0, 0}にする。

次に、上記のMを踏まえつつ、作用素Opについて考える。
いま必要なのは「kに置き換える」「kを加える」「kをかける」「k*F_iを加える」の4操作になる。
{a_i, F_i}に対して、「a_iにxをかける」「a_iにF_iのyをかけたものを加える」「a_iにzを加える」という3つを考えると、
「kに置き換える」 <=> (x,y,z) = (0,0,k)
「kを加える」 <=> (x,y,z) = (1,0,k)
「kをかける」 <=> (x,y,z) = (k,0,0)
「k*F_iを加える」 <=> (x,y,z) = (1,k,0)
で表現して、{a_i, F_i}に対して(x,y,z)を作用させると{a_i*x+F_i*y+z, F_i}になるように考えればよいことがわかる。

区間に対する操作で、要素数に応じて変化する部分を考える。
区間の要素を一様にx倍する場合は、要素をまとめあげた区間の構造に対してx倍するのと変わらないが、xを加える場合は、要素数*xが増えるので、考慮する必要がある。
要素数がlenの区間を考えている場合は、{a_i, F_i}に対して(x,y,z)を作用させると{a_i*x+F_i*y+z*len, F_i}になるように考えればよい。

作用素同士は、
{a_i, F_i} ● (a,b,c) ● (p, q, r)<=> {a*a_i + b*F_i + c, F_i} ● (p, q, r)<=> {(a*a_i + b*F_i + c)*p + q*F_i + r, F_i}<=> {a_i, F_i} ● (a*p, b*p+q, c*p+r)
より、 (a,b,c) ● (p, q, r) = (a*p, b*p+q, c*p+r)と計算してあげればよい。

作用素の単位元は、何も作用しないのと同じになる(1,0,0)を考えればよい。

ここまでで、遅延セグメント木を適用でき、十分高速に答えを求められる。
(各計算はちゃんとmodとって計算する)