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.
49 lines
1.1 KiB
49 lines
1.1 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 500010;
|
|
typedef long long LL;
|
|
LL ans;
|
|
int n;
|
|
|
|
// 似乎结构体对于线段树不友好，不准备采用
|
|
struct Node {
|
|
int val;
|
|
int id;
|
|
} b[N];
|
|
|
|
bool cmp(Node a, Node b) {
|
|
if (a.val == b.val) return a.id < b.id; // 值相等时，号小的在前
|
|
return a.val < b.val; // 值小的在前
|
|
}
|
|
|
|
int tr[N];
|
|
|
|
int lowbit(int x) {
|
|
return x & -x;
|
|
}
|
|
|
|
void add(int x, int c) {
|
|
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
|
|
}
|
|
|
|
int sum(int x) {
|
|
int res = 0;
|
|
for (int i = x; i; i -= lowbit(i)) res += tr[i];
|
|
return res;
|
|
}
|
|
|
|
int main() {
|
|
cin >> n;
|
|
for (int i = 1; i <= n; i++) {
|
|
cin >> b[i].val;
|
|
b[i].id = i;
|
|
}
|
|
sort(b + 1, b + 1 + n, cmp);
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
add(b[i].id, 1);
|
|
ans += sum(n) - sum(b[i].id); // 因为是值小的提前进场，如果值一样，则号小的先进场，那么发现有值比我小，号比我大的，就是逆序了
|
|
}
|
|
printf("%lld\n", ans);
|
|
return 0;
|
|
} |