P1908 reverse sequence pair

Tree array + discretization
The technique of discretization is to weight the order of input （ The value of the input ） Sort
Such as [5,4,2,6,3,1] The sequence obtained after sorting is [6,3,5,2,1,4]
The number of reverse pairs of the two is equal .
We can understand that ： Choose any number in this ordered sequence , For this number , All the numbers in front of it are smaller than it , If the subscript of the previous number in the original array is greater than it , Then it forms a reverse order pair .

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