57 lines
1.8 KiB
C++
57 lines
1.8 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
const int N = 500010;
|
||
typedef long long LL;
|
||
LL ans;
|
||
int n;
|
||
|
||
//每个输入的数字，我们关心两个方面：1、数值 2、位置(序号)
|
||
struct Node {
|
||
int val;
|
||
int id;
|
||
} d[N];
|
||
|
||
bool operator<(const Node &a, const Node &b) {
|
||
if (a.val == b.val) return a.id > b.id; //两个数一样大，序号大的靠前，这样统计出来的正序对才正确
|
||
return a.val > b.val; //数不一样大，数大的靠前
|
||
}
|
||
|
||
//下面是树状数组模板
|
||
int t[N];
|
||
//返回非负整数x在二进制表示下最低位1及其后面的0构成的数值
|
||
int lowbit(int x) {
|
||
return x & -x;
|
||
}
|
||
//将序列中第x个数加上k
|
||
void add(int x, int k) {
|
||
for (int i = x; i <= n; i += lowbit(i)) t[i] += k;
|
||
}
|
||
//查询序列前x个数的和
|
||
int sum(int x) {
|
||
int sum = 0;
|
||
for (int i = x; i; i -= lowbit(i)) sum += t[i];
|
||
return sum;
|
||
}
|
||
|
||
int main() {
|
||
scanf("%d", &n);
|
||
//读入每个数，分别将数值、序号记录到结构体数组d中
|
||
for (int i = 1; i <= n; i++) {
|
||
scanf("%d", &d[i].val);
|
||
d[i].id = i;
|
||
}
|
||
//对结构体数组进行排序，大的在前，小的在后；如果数值一样，序号大的在前，小的在后
|
||
sort(d + 1, d + 1 + n);
|
||
|
||
//逆序对的定义：i<j && d[i]>d[j]
|
||
// d数组是由大到小排完序的，按由大到小的顺序动态维护树状数组，计算每次变化后出现的i<j 的个数。
|
||
for (int i = 1; i <= n; i++) {
|
||
//将d[i].id放入树状数组，描述这个号的数字增加了1个
|
||
add(d[i].id, 1);
|
||
//查询并累加所有比当前节点id小的数字个数
|
||
ans += sum(d[i].id - 1);
|
||
}
|
||
//输出结果
|
||
cout << ans << endl;
|
||
return 0;
|
||
} |