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

Скажем, у меня есть три массива 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] в O (N log N) с сортировкой слияния. Я в основном ищу обобщение для трех массивов.

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

Ответ 1

Разбирая массив a и переставляя массивы b и c в одно и то же время, можно предположить, что a [i] a [j] <= > я < к. Поэтому нам нужно найти число пар (i, j), такое, что я < j, b [i] > b [j] и c [i] с [J]. Пусть вид (b [i], c [i]) как точка на плоскости. Мы добавляем точки один за другим. Каждый раз, когда мы добавляем точку (b [j], c [j]), сначала мы подсчитываем количество уже добавленных точек (i < j), так что b [i] > b [j] и c [i] < с [J]. Затем добавим точку j и переходим к следующей. Сумма чисел, полученных на каждом шаге, является нашим результатом.

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

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

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