Original Proposer: vwxyz

First, let us consider the slime-merging subproblem.
Actually, the cost is always \(\frac{(\sum_{m=1}^{M}{B_m})^2-\sum_{m=1}^{M}{B_m}^2}{2}\) regardless of the merging order.
While this can be shown inductively, we present a more intuitive proof.
Suppose that there are \(M\) groups, where the \(m\)-th group contains \(B_m\) persons.
Consider performing the following operation \((M-1)\) times: choose two groups and merge them.
If we define the cost of each operation as the product of the numbers of people contained in two groups, the cost is equivalent to that of the original problem.
For every merge, if we enumerate all pairs of persons chosen from each of the two groups, the cost of a merge operation equals the number of pairs enumerated.
Consider how many times a pair of persons \(X\) and \(Y\) is enumerated during the \((M-1)\) operations.
If persons \(X\) and \(Y\) originally belong to the same group, \((X,Y)\) is never enumerated.
If they belong to different groups, it occurs exactly once that they join to the same group, at which moment the pair is enumerated. Hence, the total cost is independent of the order of operations, and is equal to the number of pairs of persons belonging to different groups.
This number can be found by subtracting the number of pairs of persons from the same group from the number of all pairs of persons, which is \(\frac{(\sum_{m=1}^{M}{B_m})^2-\sum_{m=1}^{M}{B_m}^2}{2}\). (If person \(X\) and \(Y\) belong to different groups, person \(X\) and \(Y\) are different, so we may allow pairs of the same person to simplify the calculation.)

Next, consider how we can process the queries.
It suffices to perform the following two values: - Uniformly add the same value onto a given segment - Find the sum and sum of squares of the elements within a given segment

This can be found using a lazy segment tree that maintains for each node the following three values:

• The number of elements (degree-\(0\) sum)
• The sum (degree-\(1\) sum)
• The sum of squares (degree-\(2\) sum)

The total complexity is \(O((N+Q)\log N)\).

Bonus

The fact that the total cost is always \(\frac{(\sum_{m=1}^{M}{B_m})^2-\sum_{m=1}^{M}{B_m}^2}{2}\) regardless of operation order is used for the complexity analysis of what is called “second-order tree DP” in Japanese community (for example, as in this editorial).