Ответ 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