AcWing107 超快速排序(树状数组找逆序对)

原题链接

思路

求到底要和相邻元素交换几次，其实就是求逆序对的数量，有几对逆序对就要交换几次，因为只能相邻的之间交换(超快速排序？冒泡排序！)
利用树状数组求逆序对
大概想法是如下：
因为我们需要逆序对的数量，因此第一步就是将树状数组清空，表示当前一个数都没，然后在树状数组的第a[i]的位置上插入一个1表示当前有大小为a[i]的一个数，然后只要用i即当前位置减去sum(a[i])，即树状数组的前a[i]项的前缀和就可以知道有多少个逆序对了，因为出现了i个数字，如果第i个数在前i-1个数字的前面，那么前缀和就为i,如果比他们大在他们后面那就会少，逆序对的数量就知道了。
本题只有5e5个数字，但是a[i]非常大，直接存不现实，可以排序加个相对大小，如果在后面出现了相同的数字，比方说a[i+100]=a[i]，只要让a[i+100]的相对大小大于a[i]，那么统计前缀和也不会出错，于是我们开个ranks数组表示相对大小。

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int) (x).size()
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> VI;
typedef double db;

const int N = 5e5+10;
int n, tr[N], ranks[N]; // ranks[i]是指当前这个数的相对大小
pair<ll , int> a[N];
int lowbit(ll x) {
  return x&-x;
}
void add(int a, int b) {
  for (int i = a; i <= n; i += lowbit(i)) tr[i] += b;
}
int query(int a) {
  int res = 0;
  for (int i = a; i; i -= lowbit(i)) res += tr[i];
  return res;
}
void solve() {
  memset(tr, 0, sizeof(tr));
  memset(ranks, 0, sizeof(ranks));
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    a[i] = {x, i};
  }
  sort(a+1, a+1+n);
  ll res = 0;
  for (int i = 1; i <= n; i++) ranks[a[i].se] = i; 
  for (int i = 1; i <= n; i++) {
    add(ranks[i], 1);
    res += i-query(ranks[i]);
  }
  cout << res << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  // int tt;
  // cin >> tt;
  while (cin >> n, n) {
    solve();
  }
  return 0;
}