D - The Number of Inversions

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_D

問題文

数列 $A$ の反転数は？

バブルソートの計算回数と同じ

bubbleSort(A)
  cnt = 0 // 反転数
  for i = 0 to A.length-1
    for j = A.length-1 downto i+1
      if A[j] < A[j-1]
  swap(A[j], A[j-1])
  cnt++

return cnt

制約

• $1 \le n \le 200,000$
• 0 \l1 w \le 10^9$
• $A$ の要素はすべて異なる

サンプル

I/O 1

5
3 5 2 1 4

6

I/O 2

3
3 1 2

2

考察

えー、ライブラリを貼っただけ

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_5_D/judge/6771910/C++17

pair<ll, vector<ll>> invNum(vector<ll> a) {
  ll n = a.size();
  if (n <= 1) return { 0, a };
  ll mid = n / 2;
  auto left = invNum(vector<ll>(a.begin(), a.begin() + mid));
  auto right = invNum(vector<ll>(a.begin() + mid, a.end()));
  vector<ll> res;
  ll inv = 0;
  inv += left.first + right.first;
  ll i = 0, j = 0;
  while (i < left.second.size() && j < right.second.size()) {
    if (left.second[i] < right.second[j]) {
      res.push_back(left.second[i]);
      i++;
    }
    else {
      res.push_back(right.second[j]);
      j++;
      inv += left.second.size() - i;
    }
  }
  while (i < left.second.size()) {
    res.push_back(left.second[i]);
    i++;
  }
  while (j < right.second.size()) {
    res.push_back(right.second[j]);
    j++;
  }
  return { inv, res };
}

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  auto res = invNum(a);
  cout << res.first << endl;
  return 0;
}