Whenever the term "merging" is used in this editorial, it is referring to merging with Disjoint Set Union.

Subtask 1

We can observe that for each multiset, we only need to keep track of one node inside of it because all nodes inside of it will always be part of the same connected component. Thus, we can represent the ~N~ multisets with an array ~a~ of size ~N~, where each element ~a_i~ is either ~0~ to represent an empty multiset, or it is an arbitrary node in the multiset.

For queries of type ~1~, we simply loop through each index within ~[L_i, R_i]~ and merge ~X_i~ with ~a_i~ if it is not equal to ~0~, and then we can set ~a_i = X_i~. To output the value of the graph, we can maintain the value of the graph and update it whenever we merge.

For queries of type ~2~, let ~S~ be the set of components within ~[L_i, R_i]~. We know that no matter what node is randomly chosen, all of these components will be merged. So, we create a temporary value ~V~ that is equal to the value of the graph after the components in ~S~ are merged. We will then loop through every single node and find the value of the graph if this node was chosen. For a given node ~x~, if ~x~ is in a component that is in ~S~, the value of the graph remains as ~V~. Otherwise, the value of the graph becomes ~V - k^2 - sz(x)^2 + (k + sz(x))^2~ where ~k~ is the sum of component sizes in ~S~ and ~sz(x)~ is the size of ~x~'s component. We take the sum of all of the values for each possible node and then divide by ~M~ to find the expected value because each node has an equal chance of being chosen.

Time Complexity: ~\mathcal{O}(Q(N + M))~

Subtask 2

There are several solutions for this subtask, but we will go over the solution that most easily extends to the subtask 3 solution.

We can partition the array ~a~ into disjoint intervals where each interval is either fully empty or "points" to the same component. For each query we will loop through the intervals that intersect ~[L_i, R_i]~ and add the components to a set ~S~. Afterwards, we delete these intervals and replace it with at most ~3~ intervals: one interval will be ~[L_i, R_i]~ that points to ~X_i~, and then we will possibly need to add another interval to the left or right of this interval if we ended up erasing an interval that is only partially covered by ~[L_i, R_i]~. We will then merge everything in ~S~ and update the value of the graph. We can maintain the intervals with a set. This solution is fast because every time we loop through an interval it gets erased and we are only creating up to ~3~ intervals per query.

Time Complexity: ~\mathcal{O}(Q \log N)~

Subtask 3

The solution for this subtask is almost the same as subtask ~2~, except we need to instead add an interval that points to ~0~ for type ~2~ queries and also do a bit of math for the expected value. Let ~S~ be the set of components within the interval ~[L_i, R_i]~, let ~k~ be the sum of component sizes in ~S~, and let ~V~ be the value of the graph after merging these components.

For nodes that are part of ~S~, when we choose them the value of the graph will still be ~V~. Taking the sum of all of the values after choosing these nodes, we get ~V * k~.

Let ~x~ be a node that is not part of ~S~. If we choose ~x~, the value of the graph will be ~V - k^2 - sz(x)^2 + (k + sz(x))^2~ where ~sz(x)~ is the size of node ~x~'s component. Expanding the expression, we get ~V + 2 * k * sz(x)~. Taking the sum across all nodes ~x~ that are not part of ~S~, we get ~V * (M - k) + 2 * k * sq~ where ~sq~ is the sum of squares of all component sizes of ~x~ and can be computed easily after looping through ~S~.

Finally, since each node has an equal chance of being chosen, we can see that the expected value of the graph is ~\frac{V * k + V * (M - k) + 2 * k * sq}{M}~.

Time Complexity: ~\mathcal{O}(Q \log N)~