原案:vwxyz

まず、スライムを合成する問題について考えます。
実は、合成の順番によらず、コストは必ず \(\frac{(\sum_{m=1}^{M}{B_m})^2-\sum_{m=1}^{M}{B_m}^2}{2}\) に等しくなります。
帰納法などでも証明できますが、もっと直感的な方法でこれを証明します。
\(M\) 個のグループがあって、\(m\) 番目のグループは \(B_m\) 人からなるとします。
\(2\) つのグループを選んでマージするという操作を \(M-1\) 回行うことにします。
各操作のコストをマージする \(2\) つのグループに含まれる人の数の積とすると、これは元の問題のコストに一致します。
ここで、マージが行われるたびに \(2\) つのグループからそれぞれ \(1\) 人ずつ選んだ \(2\) 人の組をすべて列挙することにすると、操作のコストは列挙される組の総数に等しいです。
\(M-1\) 回の操作において人 \(X\) と \(Y\) の組が列挙される回数について考えます。 人 \(X\) と \(Y\) が元から同じグループに属している場合、\((X,Y)\) が列挙されることはありません。
違うグループに属している場合、マージされることで同じグループに属すことになる瞬間がちょうど \(1\) 回存在し、そのときにだけ列挙されることになります。
よって、コストの総和は操作順によらず、異なるグループに属する人の組の総数に等しいことがわかります。
\(2\) 人の組の総数から同じグループに属する \(2\) 人の組の総数を引いてこの値を求めることにすると、これは \(\frac{(\sum_{m=1}^{M}{B_m})^2-\sum_{m=1}^{M}{B_m}^2}{2}\) に等しいことがわかります。 （人 \(X,Y\) が異なるグループに属するならば \(X\) と \(Y\) は違う人であることから、同じ人を選んでもいいような組も許容して考えるとわかりやすいです）

次に、クエリを処理することを考えます。
以下の \(2\) つの処理ができればよいです。

• 区間に同じ値を加算する
• 区間内の和と\(2\) 乗和を求める

これは、各区間内における以下の \(3\) つの値をもって遅延伝播セグメント木を用いて求めることができます。

• 個数（\(0\) 乗和）
• 総和（\(1\) 乗和）
• \(2\) 乗和

全体の計算量は \(O((N+Q)\log N)\) です。

余談

コスト総和が操作順によらず \(\frac{(\sum_{m=1}^{M}{B_m})^2-\sum_{m=1}^{M}{B_m}^2}{2}\) であることは、\(2\) 乗の木 dp の計算量解析に用いることができます。