题目：

珂朵莉给了你一个序列，有个子区间，求出她们各自的逆序对个数，然后加起来输出。
对于100%的数据，n <=1000000 ,0 <= 序列中每个数 <= 1000000000

做法：

换个角度，题目要我们求的是每个逆序对在多少个子区间内。那么对于一个逆序对，它的贡献就是理解为，任选一个位置，任选一个位置，区间是一个包含逆序对的子区间。
序列中第个位置作为第二个数的逆序对，就是在中找多少个比大的数。现在假如我们知道在中比大的数的位置和。那么第个位置作为第二个数的所有逆序对的子区间贡献就等于。这个我们离散化之后用线段树维护。问题就解决了。具体怎么维护的请看代码。
PS：这题数据爆longlong，用__int128可过。

代码：

#include <bits/stdc++.h>
#define lson (rt<<1)
#define rson (rt<<1|1)
#define debug(a) cout << #a ": " << a << endl
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef __int128 ll;
inline int read(void){
    char ch = getchar();
    int ans = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) ans = ans*10+ch-'0', ch = getchar();
    return ans;
}
const int N = 1e6 + 7;
int n, m, a[N], b[N];
vector<int> h;
ll T[N<<2];
int get(int x){
    return lower_bound(h.begin(), h.end(), x)-h.begin()+1;
}
void update(int pos, ll add, int l, int r, int rt){
    if (l == r){
        T[rt] += add; return;
    }
    int mid = (l+r) >> 1;
    if (pos <= mid) update(pos, add, l, mid, lson);
    else update(pos, add, mid+1, r, rson);
    T[rt] = T[lson]+T[rson];
}
ll query(int L, int R, int l, int r, int rt){
    if (L > R) return 0;
    if (L <= l && r <= R){
        return T[rt];
    }
    int mid = (l+r) >> 1;
    ll ans = 0;
    if (L <= mid){
        ans += query(L, R, l, mid, lson);
    }
    if (R > mid){
        ans += query(L, R, mid+1, r, rson);
    }
    return ans;
}
void Print(ll x){
    if (x == 0) return;
    Print(x/10);
    int dig = x%10;
    printf("%d", dig);
}
int main(void){
    n = read();
    for (int i = 1; i <= n; ++i){
        a[i] = read();
        h.push_back(a[i]);
    }
    sort(h.begin(), h.end());
    h.erase(unique(h.begin(), h.end()), h.end());
    m = h.size();
    for (int i = 1; i <= n; ++i){
        a[i] = get(a[i]);
        b[i] = i;
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i){
        ll lef = query(a[i]+1, m, 1, m, 1);
        ll rig = n-i+1;
        ans += lef*rig;
        update(a[i], b[i], 1, m, 1);
    }
    if (ans == 0) printf("0\n");
    else Print(ans);
    return 0;
}