Инверсии счетчика в двух массивах

Инверсия в массиве представляет собой пару индексов (i, j) таких, что a [i] > a [j] и я < к.

Учитывая 2 массива A и B, и мы должны вернуть число таких пар таким, что a [i] > b [j] и я < к.

Пример:

Пусть n = 3 и A [] = [5,6,7] и B [] = [1,2,3], тогда ответ равен 3. 3 пары: (5,2), (5,3) и (6,3).

Мой код:

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int len;
    scanf("%d",&len);
    int a[len];
    int b[len];
    for(int i = 0; i < len; i++)
       scanf("%d",&a[i]);
    for(int i = 0; i < len; i++)
       scanf("%d",&b[i]);
    int count = 0;
    for (int i = 0;i < len; i++)
    {
        for(int j = i+1; j < len; j++)
        {
             if(a[i] > b[j])
             {
                 count++;
             }
         }
     }
     printf("%d",count);
}

Но это решение O (N ^ 2). Мне нужно лучшее решение как N <= 200000. Я знаю, что мы можем подсчитывать инверсии в одном массиве в O (N * Log N). Но как это можно сделать для двух разных массивов?

Ответы

Ответ 1

Я уже о том, как считать инверсии с помощью Fenwick tree, который является очень эффективным типом двоичного дерева, которое позволяет вычислять агрегаты префикса в последовательности.

Ниже приведен пример adhoc modifcation для вашего сценария:

long long inversions(const vector<int>& a, const vector<int>& b) {
  int n = a.size();
  vector<int> values(a);
  for (int x: b) values.push_back(x);
  sort(begin(values), end(values));
  vector<int> counts(2*n + 1);
  long long res = 0;
  for (int i = n - 1; i >= 0; --i) {
    // compute sum of prefix 1..rank(a[i]) - 1
    for (int v = lower_bound(begin(values), end(values), a[i]) - begin(values);
         v; 
         v -= v & -v)
      res += counts[v];
    //add 1 to point rank(b[i])
    for (int v = lower_bound(begin(values), end(values), b[i]) - begin(values) + 1;
         v <= 2*n;
         v += v & -v)
      counts[v]++;
  }
  return res;
}

В основном мы просматриваем массивы справа налево, поддерживая структуру данных, которая представляет значения, которые мы уже видели в суффиксе. Для каждого элемента b [i] мы добавляем к окончательному результату число элементов x в структуре данных с x <= b [i] - 1. Затем мы добавляем [i] к структуре данных.

Массив values используется для сжатия диапазона значений до 1..2n, потому что деревья Фенвика занимают пространство, линейное по размеру диапазона. Мы могли бы избежать этого шага, выбирая более полнофункциональную структуру данных, такую ​​как сбалансированное дерево поиска bjnary с расширением размера поддерева.

Сложность - O (n log n), а постоянный коэффициент очень низкий.

Ответ 2

Одна идея:
1. Слейте два оригинальных массива так, чтобы каждая пара элементов с одинаковыми индексами смежна с другими. (Вам нужно будет поместить элементы таким образом, чтобы нижняя была выше предыдущей).
3. Подсчитайте количество инверсий в результирующем массиве, как описано ниже.

Изменить: извините, я неправильно истолковал вопрос. Если вам нужны инверсии только от (I) до b (j), вы можете пометить каждый элемент другим типом массива полей (a или b). Затем, в то время как mergesorting вы можете увеличивать счетчик только в том случае, если инверсия от массива a до b.