Modo efficiente per trovare ordini di coppia?

Question

Diciamo che ho tre array a, b e c di uguale lunghezza N. Gli elementi di ciascuno di questi array provengono da un totally ordered set, ma non sono ordinati. Ho anche due variabili di indice, i e j. Per tutti i != j, voglio contare il numero di coppie di indice tale che a[i] < a[j], b[i] > b[j] e c[i] < c[j]. Esiste un modo in cui ciò può essere fatto in meno di O (N^2) complessità temporale, ad esempio mediante l'uso creativo degli algoritmi di ordinamento?

Note: L'ispirazione per questa domanda è che, se hai solo due array, a e b, è possibile trovare il numero di coppie di indice in modo tale che a[i] < a[j] e b[i] > b[j]in O(N log N) with a merge sort. Sto fondamentalmente cercando una generalizzazione a tre matrici.

Per semplicità, si può presumere che due elementi di qualsiasi matrice sono uguali (legami).

Answer 1

Ordinando l'array a e riordinando gli array be c allo stesso tempo, possiamo supporre che un [i] a [j] < => i < j. Quindi dobbiamo trovare il numero di coppie (i, j) tali che io sia < j, b [i]> b [j] e c [i] < c [j]. Vediamo (b [i], c [i]) come un punto su un piano. Aggiungiamo i punti uno per uno. Ogni volta che si aggiunge un punto (b [j], c [j]), dapprima si conta il numero di punti già aggiunte (i < j) tale che b [i]> b [j] e c [i] < c [j]. Quindi aggiungiamo il punto j e passiamo al prossimo. La somma dei numeri ottenuti ad ogni passo è il nostro risultato.

Ora sembra che questo tipo di query possa essere soddisfatto da un albero di segmenti bidimensionale: http://en.wikipedia.org/wiki/Segment_tree Il costo di una iterazione sarà O (log^2 n), e la complessità totale è O (n log^2 n).

(noti che qui assumo che gli elementi di matrici sono numeri. Va bene, perché l'utilizzo di un ordinamento possiamo sempre sostituire gli elementi di una matrice con i numeri da 1 a n in modo che l'ordine è stato conservato.)

Modifica: In realtà, una struttura più semplice chiamata albero di Fenwick o albero indicizzato binario è sufficiente. Vedere questo link: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees#2d