解説

遅延セグメント木で扱いやすそうな問題なので、その方針で考えます。

1. ノードに何を持たせるか

各ノードには、その区間に対応する

• この区間単体での答え (ans)
• 区間の総和 (sum)

を持たせることを考えます。必要になれば後から情報を追加します。

以下では、遅延セグメント木の用語は ACL のものを用います。

---

2. op を考える

左右の子が表す数列をそれぞれ

• 左：X
• 右：Y

とします。

数列 X + Y（連結した数列）の答えを考えると、

• 左区間だけで発生するコスト
• 右区間だけで発生するコスト
• 左右を最後に合成するときに発生するコスト

の 3 つに分けられます。

最後の合成では、左側全体の重さは sum(X)、右側全体の重さは sum(Y) なので、追加コストは

\[ \mathrm{sum}(X)\times\mathrm{sum}(Y) \]

となります（以降、mod 998244353 は省略）。

したがって、

\[ \mathrm{ans}(X+Y) = \mathrm{ans}(X) + \mathrm{ans}(Y) + \mathrm{sum}(X)~\mathrm{sum}(Y) \]

が成り立ちます。

この式はどこで区間を分割しても成立するため、区間を適当に左右へ分ける遅延セグメント木と非常に相性が良いです。

よって op は

• ans を上式で更新する
• sum を加算する

だけで実装できます。

---

3. composition を考える

\(a+b\) を return すればよいです。

4. mapping を考える

区間加算を行うためには、区間の長さも必要になります。

そこで各ノードには

• ans
• sum
• len

の 3 つを持たせます。

区間内のすべての要素に x を加えたときの変化を考えます。

元の値を a とすると、新しい値は a+x です。

新しい答えは次の 3 種類の寄与に分けられます。

• 元々あった要素同士 これは変化しないので ans。

• 元の値と追加した値の組 各要素は最終的に他の len-1` 個の要素と組になるため、 \( x \times \mathrm{sum}\times(\mathrm{len}-1) \) 。

• 追加した値同士の組 各組について x^2 が寄与し、その組数は \( \binom{\mathrm{len}}2= \frac{\mathrm{len}(\mathrm{len}-1)}2 \) なので、

\[ x^2\frac{\mathrm{len}(\mathrm{len}-1)}2 .\]

以上より、遅延セグメント木が設計できました。

実装例 https://atcoder.jp/contests/abc455/submissions/75259748