結論から言うと、クエリ平方分割で O(N√Q log(max {A}) + Q(√Q + logQ)) で解けます。
問題概要
考えたこと
クエリ 1 が曲者で、通常の遅延セグメント木には乗せられないため、仕方なく「困ったときの平方分割」をしてみる。
√Q 回のクエリを 1 ブロックとしてまとめると、クエリ全体として √Q 個のブロックがあることになる。
したがって、ブロックあたりおよそ O(N logN) くらいに収めることを考える。
前述の通り、1 ブロックあたりのクエリ回数は √Q 回なので、クエリ区間の切れ目も高々 2√Q 箇所である。
そこで、高々 (2√Q + 1) 個に細分化した区間に対して、それぞれ高々 √Q 回のクエリを行う。
区間の細分化には座標圧縮を伴い、O(√Q logQ) である。
区間内の全要素が等しい場合、1 つの値のみを変化させるだけになるので、どのクエリも O(1) で実行可能である。
なお、ブロック内の全区間に対する全クエリを終わらせたあとで、数列 A に値を代入することになるため、その計算に O(N) かかる。
次に、区間内の要素が異なる場合を考える。
クエリ 2 は、区間内の全要素を等しくする効果があるので、1 区間に対して 1 つの値のみを保持すれば良いことになる。
また、クエリ 3 については、クエリ 1 を行うごとに区間 sum を計算しておけばよい。
どちらも実質的に O(1) になる。
続いて問題のクエリ 1 については、高々 log(max {A}) 回行えば区間内の全要素が 0 になる。
各要素を愚直に除算するとして、区間 [L, R) に対して 1 回あたり O(R - L) で済むので、全区間全クエリでは O(N log(max {A})) で収まる。
以上を踏まえると、ブロックあたりの計算量は O(N log(max {A}) + Q + √Q logQ) となる。
これを √Q ブロック分繰り返せば良い。
