We will use the union-find data structure in solving this task.

Let's first describe the solution that isn't fast enough, but serves as a motivation for the actual solution.

What data must be remembered in each component? Each component corresponds to a set of positions. Let's denote the multiset of all values contained in the array ~p~ on positions contained in component ~K~ with ~P_K~, and the multiset of all values contained in the sorted array ~q~ on positions contained in component ~K~ with ~Q_K~. When joining components ~A~ and ~B~ into a new component ~C~, we see that ~P_C = P_A \cup P_B~ and ~Q_C = Q_A \cup Q_B~.

It is crucial to notice that the array can be sorted if and only if ~P_K = Q_K~ holds for each component.

After this, we can notice that it is not necessary to remember the exact multisets of numbers, but only their hash values. If number ~1~ is contained ~c_1~ times in multiset ~S~, number ~2~ ~c_2~ times, …, ~n~ ~c_n~ times, then we define the hash value of set ~S~ as:

$$\displaystyle h(S) = c_1 H + c_2 H^2 + \dots + c_{n-1} H^{n-1}$$

When joining components, we simply add the hash values of the original components.

But, we still haven't mentioned how to answer query number 4. We actually want to know the number of pairs such that it holds:

~P_A+P_B = Q_A+Q_B~ (where now ~P~ and ~Q~ denote the hash values) ~\iff P_A-Q_A = -(P_B-Q_B)~

Now we know how to answer the query by maintaining map ~M~ where ~M[d]~ tells us how many nodes there are with the component's difference ~P-Q~ being exactly ~d~.

The time complexity of this solution is ~\mathcal O(Q \log N)~.