Эффективный способ найти парные заказы?

Question

Допустим, у меня есть три массива a, b и c равной длины N. Элементы каждого из этих массивов происходят из полностью упорядоченного набора , но не сортируются. У меня также есть две индексные переменные, i и j. Для всех i != j я хочу посчитать количество пар индексов, таких как a[i] < a[j], b[i] > b[j] и c[i] < c[j]. Есть ли способ сделать это менее чем за O (N ^ 2) сложность времени, например, путем творческого использования алгоритмов сортировки?

Примечания. Источником этого вопроса является то, что если у вас есть только два массива, a и b, вы можете найти число пар индексов, таких как a[i] < a[j] и b[i] > b[j] в (N log N) с сортировкой слиянием . Я в основном ищу обобщение до трех массивов.

Для простоты вы можете предположить, что никакие два элемента любого массива не равны (нет связей).

Answer 1

Сортируя массив a и переставляя массивы b и c одновременно, мы можем предположить, что a [i] i b [j] и c [i] b [j] и c [i]

Теперь кажется, что этот вид запросов может быть выполнен с помощью двумерного дерева сегментов:

http://en.wikipedia.org/wiki/Segment_tree Стоимость одной итерации будетO (log ^ 2 n), а общая сложность равна O (n log ^ 2 n).

(Обратите внимание, что здесь я предполагаю, что элементы массивов являются числами. Это нормально, потому что при использовании сортировки мывсегда можно заменить элементы массива числами от 1 до n, чтобы порядок был сохранен.)

Редактировать: Фактически, достаточно более простой структуры, называемой деревом Фенвика или двоичным индексированным деревом.Смотрите эту ссылку: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees#2d