python/TangDou/AcWing/P1908.cpp

#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;
}