¿Manera eficiente de encontrar órdenes de par?

Question

Digamos que tengo tres matrices a, b y c de igual longitud N. Los elementos de cada una de estas matrices provienen de un totally ordered set, pero no están ordenados. También tengo dos variables de índice, i y j. Para todos i != j, quiero contar el número de pares de índices tales como a[i] < a[j], b[i] > b[j] y c[i] < c[j]. ¿Hay alguna manera de que esto se pueda hacer en menos de O (N^2) complejidad de tiempo, por ejemplo mediante el uso creativo de algoritmos de clasificación?

Notas: La inspiración para esta pregunta es que, si sólo tiene dos matrices, a y b, puede encontrar el número de pares de índice tal que a[i] < a[j] y b[i] > b[j]in O(N log N) with a merge sort. Básicamente estoy buscando una generalización para tres arreglos.

Para simplificar, puede suponer que no hay dos elementos de ninguna matriz iguales (sin vínculos).

Answer 1

Al ordenar la matriz a y al reorganizar las matrices byc al mismo tiempo, podemos suponer que a [i] < a [j] < => i < j. Por lo tanto, necesitamos encontrar el número de pares (i, j) tal que i < j, b [i]> b [j] y c [i] < c [j]. Veamos (b [i], c [i]) como un punto en un plano. Agregamos los puntos uno por uno. Cada vez que agregamos un punto (b [j], c [j]), primero contamos el número de puntos ya agregados (i < j) de modo que b [i]> b [j] y c [i] < c [j]. Luego agregamos el punto j y pasamos al siguiente. La suma de los números obtenidos en cada paso es nuestro resultado.

Ahora parece que este tipo de consultas pueden cumplirse mediante el árbol de segmento bidimensional: http://en.wikipedia.org/wiki/Segment_tree El costo de una iteración será O (log^2 n), y la complejidad total es O (n log^2 n)

(Tenga en cuenta que Asumo aquí que los elementos de las matrices son números. Está bien, porque el uso de una selección que siempre se puede sustituir los elementos de una matriz con los números del 1 al n de modo que el orden fue preservada.)

Editar: De hecho, una estructura más simple llamada árbol de Fenwick o árbol indexado binario es suficiente. Ver este enlace: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees#2d