思路
求到底要和相邻元素交换几次,其实就是求逆序对的数量,有几对逆序对就要交换几次,因为只能相邻的之间交换(超快速排序?冒泡排序!)
利用树状数组求逆序对
大概想法是如下:
因为我们需要逆序对的数量,因此第一步就是将树状数组清空,表示当前一个数都没,然后在树状数组的第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;
}
标签:typedef,AcWing107,树状,int,数组,逆序,define
From: https://www.cnblogs.com/chelly-algorithm/p/16826198.html