|
|
/*
|
|
|
逆序对数量：
|
|
|
归并排序解法 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;
|
|
|
} |
