P1908 逆序对

树状数组+离散化
离散化的技巧就是给输入的顺序按权值（输入的值）排序
如 [5,4,2,6,3,1] 排完序后得到的顺序序列就是 [6,3,5,2,1,4]
两者的逆序对数量相等。
我们可以这么理解：在这个有序序列中任意选一个数，对于这个数来说，它前面的所有数都小于它，如果前面数在原数组中的下标大于它，则构成一个逆序对。

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

struct fenwick {
    
    const int n;
    std::vector<int> c;
    fenwick(int n) : c(n + 10), n(n + 10) {
    }
    void add(int pos, int val) {
    
        for (int i = pos; i < n; i += i & -i) {
    
            c[i] += val;
        }
    }
    int sum(int pos) {
    
        int ans = 0;
        for (int i = pos; i > 0; i -= i & -i) {
    
            ans += c[i];
        }
        return ans;
    }
    int range(int l, int r) {
     return std::abs(sum(r) - sum(l)); }
};


constexpr int N = 5e5 + 100;

pair<int, int> a[N];

void solve() {
    
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
    
        cin >> a[i].first;
        a[i].second = i + 1;
    }
    sort(a, a + n);

    int ans = 0;

    fenwick f(n);
    for (int i = 0; i < n; i++) {
    
        ans += f.range(a[i].second, n);
        f.add(a[i].second, 1);
    }   
    cout << ans << "\n";
}   


int32_t main() {
    
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int tt(1);
    //std::cin >> tt;

    while (tt--) {
    
        solve();
    }

    return 0;
}