Usaremos la estructura de datos union-find para resolver esta tarea. Primero describamos la solución que no es lo suficientemente rápida, pero que sirve como motivación para el solución real. ¿Qué datos se deben recordar en cada componente? Cada componente corresponde a un conjunto de posiciones. Denotemos el conjunto múltiple de todos los valores contenidos en la matriz ~p~ en las posiciones contenidas en la componente ~K~ como ~P_K~, y el conjunto múltiple de todos los valores contenidos en el arreglo ordenado ~q~ en posiciones contenidas en la componente ~K~ como ~Q_K~. Al unir los componentes ~A~ y ~B~ en un nuevo componente ~C~, vemos que \(P_C = P_A ∪ P_B\) y \(Q_C = Q_A ∪ Q_B\). Es crucial notar que el arreglo se puede ordenar si y solo si ~P_K = Q_K~ se cumple para cada componente.

Después de esto, podemos notar que no es necesario recordar los conjuntos múltiples de números exactos, sino solo sus valores hash. Si el número ~1~ está contenido ~c_1~ veces en multiset ~S~, el número ~2~ ~c_2~ veces, ... ~n~ ~c_n~ veces, entonces definimos el valor hash del conjunto S como:

~h (S) = c_1 \cdot H^1 + c_2 \cdot * H^2 + ... + c_n \cdot H^n~

Al unir componentes, simplemente agregamos los valores hash de las componentes originales.

Sin embargo, todavía no hemos mencionado cómo responder a la consulta número 4. De hecho, queremos saber el número de pares que contiene: ~P_A + P_B = Q_A + Q_B~ (donde ahora ~P~ y ~Q~ denotan los valores hash)

Entonces ~P_A - Q_A = - (P_B - Q_B)~ Ahora sabemos cómo responder a la consulta manteniendo el mapa ~M~ donde ~M_d~ nos dice cuántos nodos hay con la diferencia de ~P - Q~ siendo exactamente ~d~. La complejidad temporal de esta solución es ~O (Q\log N)~.