87 lines
2.3 KiB
C++
87 lines
2.3 KiB
C++
/*
|
||
逆序对数量：
|
||
归并排序解法 https://blog.csdn.net/m0_50299150/article/details/122729602
|
||
树状数组解法 https://blog.csdn.net/m0_50299150/article/details/122729602
|
||
权值线段树解法
|
||
*/
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
typedef long long LL;
|
||
const int N = 5e5 + 10;
|
||
int a[N];
|
||
vector<int> nums;
|
||
//手写二分版本+离散化 325 ms
|
||
int n;
|
||
struct node {
|
||
int l, r, sum;
|
||
} tr[N << 2];
|
||
|
||
void build(int root, int l, int r) {
|
||
tr[root] = {l, r, 0};
|
||
if (l == r) return;
|
||
int mid = (l + r) >> 1;
|
||
build(root << 1, l, mid);
|
||
build(root << 1 | 1, mid + 1, r);
|
||
}
|
||
void pushup(int root) {
|
||
tr[root].sum = tr[root << 1].sum + tr[root << 1 | 1].sum;
|
||
}
|
||
void modify(int root, int pos, int val) {
|
||
if (tr[root].l == pos && tr[root].r == pos) {
|
||
tr[root].sum += val;
|
||
return;
|
||
}
|
||
int mid = tr[root].l + tr[root].r >> 1;
|
||
if (mid >= pos)
|
||
modify(root << 1, pos, val);
|
||
else
|
||
modify(root << 1 | 1, pos, val);
|
||
pushup(root);
|
||
}
|
||
int query(int root, int l, int r) {
|
||
if (tr[root].l == l && tr[root].r == r) return tr[root].sum;
|
||
int mid = tr[root].l + tr[root].r >> 1;
|
||
if (mid < l)
|
||
return query(root << 1 | 1, l, r);
|
||
else {
|
||
if (r <= mid)
|
||
return query(root << 1, l, r);
|
||
else
|
||
return query(root << 1, l, mid) + query(root << 1 | 1, mid + 1, r);
|
||
}
|
||
}
|
||
//改成手写二分查询，AC掉洛谷此题
|
||
int find(int x) {
|
||
int l = 0, r = nums.size() - 1;
|
||
while (l < r) {
|
||
int mid = (l + r) >> 1;
|
||
if (nums[mid] >= x)
|
||
r = mid;
|
||
else
|
||
l = mid + 1;
|
||
}
|
||
return l + 1;
|
||
}
|
||
int main() {
|
||
//优化读入
|
||
ios::sync_with_stdio(false);
|
||
cin >> n;
|
||
for (int i = 1; i <= n; i++) {
|
||
cin >> a[i];
|
||
nums.push_back(a[i]);
|
||
}
|
||
//离散化
|
||
sort(nums.begin(), nums.end());
|
||
nums.erase(unique(nums.begin(), nums.end()), nums.end());
|
||
|
||
LL ans = 0;
|
||
build(1, 1, nums.size() + 1);
|
||
//边查边添加,查找它后面比它大的数字个数
|
||
for (int i = 1; i <= n; i++) {
|
||
int p = find(a[i]);
|
||
ans += query(1, p + 1, nums.size() + 1);
|
||
modify(1, p, 1);
|
||
}
|
||
cout << ans << endl;
|
||
return 0;
|
||
} |