Блог пользователя eduardG

Автор eduardG, 6 лет назад, По-русски

С помощью каких алгоритмов, кроме сортировки слиянием, можно найти количество инверсий в массиве?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

С помощью любой структуры данных, которая умеет делать обновление в точке и считать сумму на отрезке. Например, с помощью Дерева Отрезков или Дерева Фенвика. Изначально в структуре нули. Будем идти по нашему массиву v и прибавлять в точке v[i] единицу. Теперь, когда стоим в i, прибавим к кол-ву инверсий sum(v[i] + 1, INF). Это верно, так как мы по факту учитываем все числа, которые больше нашего, но встретились нам раньше. Тогда асимптотика будет O(NlogN).

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Можно идти с конца и поддерживать какой-нибудь массив P. Пусть мы сейчас находимся на каком-нибудь элементе A[i] нашего массива. Тогда мы в массиве P на позиции A[i] прибавим единицу (то есть, скажем, что такое число встретилось у нас на суффиксе). Тогда чему равно кол-во инверсий для текущего элемента в массиве A[i]? Правильно — сумма всех чисел в массиве P на всех индексах, начиная с 1 и заканчивая A[i]-1. Для операции обновления суммы можно использовать ДО. И да, если числа в массиве большие, то можно сначала сжать их. От этого наш ответ не поменяется.

»
5 месяцев назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

Без объяснений, просто моя реализация с использованием Дерева Фенвика вместо Дерева Отрезков. + Делаю сжатие координат, т.е. превращаю массив из -1, -7, 0, 4, -1 в 1, 0, 2, 3, 1чтобы работало на $$$a_i \in [-10^9; +10^9]$$$

// semenInRussia 2024
#include <algorithm>
#include <iostream>
using namespace std;

const int maxn = 1e5 + 100;
int t[maxn], a[maxn], b[maxn];
int qry(int r) {
  int res = 0;
  for (; r > 0; r -= r & -r)
    res += t[r];
  return res;
}

void add(int k, int v) {
  for (; k <= maxn; k += k & -k)
    t[k] += v;
}

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> a[i], b[i] = a[i];
  sort(b, b + n);
  using ll = long long;
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    int id = lower_bound(b, b + n, a[i]) - b;
    // count which is more at left.
    ans += i - qry(id + 1);
    add(id + 1, 1);
  }
  cout << ans;