hackercupai/hackercup huggingface dataset:
Each query depends only on the number of \(1\)s, \(2\)s, and \(3\)s present in each of the two subarrays. These counts can be computed in \(\mathcal{O}(\log N)\) time per query if three Fenwick trees, one per possible value, are maintained (in a total of \(\mathcal{O}((N+M) \log N)\) time), storing a bit for whether each index contains the value for that tree.

When it comes to evaluating each query, letting \(d\) be the difference between the subarrays' sums, our goal is to reduce \(d\) to \(0\). If we denote the subarray with the lower sum as \(L\), and the one with the higher sum as \(H\), we can influence \(d\) in the following relevant ways:

1. Decrease \(d\) by \(4\) by swapping a \(1\) in \(L\) with a \(3\) in \(H\).
2. Decrease \(d\) by \(2\) by swapping a \(1\) in \(L\) with a \(2\) in \(H\), or a \(2\) in \(L\) with a \(3\) in \(H\).
3. Increase \(d\) by \(2\) by swapping a \(2\) in \(L\) with a \(1\) in \(H\), or a \(3\) in \(H\) with a \(2\) in \(H\).

Note that it's impossible to decrease \(d\) by an odd number with any swap, since if the difference between two swapped numbers is \(v\), then the sum of \(L\) will increase by \(v\) while the sum of \(H\) will decrease by \(v\), so \(d\) itself will change by \(2v\). Therefore, we can immediately report \(-1\) if \(d\) is odd.

Otherwise, we can greedily perform #1 as many times as possible without \(d\) becoming too small. One strategy is to perform #1 until either \(d < 4\), or we run out of pairs of \(1\)s and \(3\)s to swap in \(L\) and \(H\), and then perform #2 the rest of the way. Another strategy is to perform #1 until \(d\) drops to \(-2\), and then perform #3 once. We should consider both strategies (if possible) and take the one which uses fewer swaps.

To implement the two strategies, we can find the \(6\) counts of \(1\)s, \(2\)s, and \(3\)s across the two subarrays in \(\mathcal{O}(\log N)\) time with Fenwick tree queries, then simulate the swaps in \(\mathcal{O}(1)\) time.

[See David Harmeyer's solution video here.](https://youtu.be/3tuCyPdU2fo)