You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

80 lines
2.1 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

/*
逆序对数量:
归并排序解法 https://blog.csdn.net/m0_50299150/article/details/122729602
树状数组解法 https://blog.csdn.net/m0_50299150/article/details/122729602
权值线段树解法
*/
// 446 ms
//此方法vector+离散化+STL二分查找在AcWing 可以正常通过在洛谷挂一半TLE,怀疑是lower_bound太慢
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int a[N];
vector<int> nums;
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);
}
}
int find(int x) {
return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 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;
}