Mixing MEXes

Let the original MEX of array $a_i$ be $m_i$, and let

$S=\sum_{i=1}^{n} m_i, \qquad L=\sum_{i=1}^{n} |a_i|.$

There are $L(n-1)$ possible operations, because every element occurrence can be moved to any other array. If nothing changed, every operation would contribute $S$, so the baseline is

$S\cdot L\cdot(n-1).$

Now stop thinking about the whole operation. Only two arrays matter: the source loses one element, and the destination gains one element. Everyone else just sits there looking busy.

For an operation moving value $x$ from source $i$ to destination $k$, its value is

$S + \Delta^-_i(x) + \Delta^+_k(x),$

where $\Delta^-_i(x)$ is the MEX change after removing this specific occurrence from $a_i$, and $\Delta^+_k(x)$ is the MEX change after adding $x$ to $a_k$.

For removing, suppose $\operatorname{MEX}(a_i)=m$.

If $x\ge m$, removing $x$ cannot affect the presence of all values $0,1,\dots,m-1$, and $m$ was already missing. So the MEX stays $m$.

If $x<m$, then $x$ is currently present. Removing it only matters if it was present exactly once. In that case $x$ becomes the smallest missing number, so the new MEX is $x$.

Therefore

$$\Delta^-_i(x)= \begin{cases} x-m, & x<m \text{ and } \operatorname{freq}_i(x)=1,\\ 0, & \text{otherwise.} \end{cases}$$

This delta is counted once for every possible destination, so the total removal contribution is

$$(n-1)\sum_i\sum_{x<m_i,\ \operatorname{freq}_i(x)=1}(x-m_i).$$

For adding, again let $\operatorname{MEX}(a_k)=m$.

Adding $x$ changes the MEX only if $x=m$, because $m$ is the first missing value. If $x\ne m$, then $m$ is still missing, so the MEX remains $m$.

When we add $m$, the new MEX becomes the first missing value greater than $m$. Call it $nxt_k$. Then

$$\Delta^+_k(x)= \begin{cases} nxt_k-m_k, & x=m_k,\\ 0, & \text{otherwise.} \end{cases}$$

For destination $k$, this delta is paid for every occurrence of value $m_k$ outside array $k$. Since $m_k$ is missing from $a_k$, that is just the global number of occurrences of $m_k$.

So the total addition contribution is

$$\sum_k (nxt_k-m_k)\cdot cnt[m_k].$$

Combine everything:

$$\boxed{ S\cdot L\cdot(n-1) +(n-1)\sum_i\sum_{x<m_i,\ \operatorname{freq}_i(x)=1}(x-m_i) +\sum_k (nxt_k-m_k)\cdot cnt[m_k] }$$

To compute the data for one array, count only values up to $|a_i|+1$. An array of length $l$ cannot force its MEX or next missing value past $l+1$, so huge values are MEX noise.

For each array:

1. Build local frequencies for relevant values.
2. Scan upward to find $m_i$.
3. Continue scanning to find $nxt_i$.
4. Add $x-m_i$ for every locally touched $x<m_i$ with frequency $1$.
5. Add $(nxt_i-m_i)\cdot cnt[m_i]$ to the addition contribution.

All arithmetic should be long long. Complexity is

$O\left(n+\sum_i |a_i|\right)$

per test case, with linear memory. Reset only touched frequency entries; clearing giant arrays every test is the kind of tiny-looking mistake that nukes performance.