题意

珂朵莉给了你一个长度为的序列，有个子区间，求所有区间逆序对的个数和。

分析

比如说我们选择有一对逆序对，，那么以为结尾的逆序对，所产生的贡献是，

区间左边有个选择，区间右边也有个选择。

现在我们统计假设区间是，那么以为结尾的逆序对，所产生的贡献是。

所以我们可以发现就是统计前面比它大的数的下标和乘以自己后面的下标个数。

然后我们可以离散化，然后统计比我大的数不好统计，我们可以反过来，把当成，把当成

，去统计比我小的数。

最后注意精度问题就好了，int__128_t真香。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int __int128_t
const int inf = 0x3f3f3f3f;
const int maxn = 1001110;
const int M = 1e9+7;
int n,m;

int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return f*x;
}

void print(int x)
{
    if(x < 0) {putchar('-');x = -x;}
    if(x/10) print(x/10);
    putchar(x%10+'0');
}

int a[maxn],b[maxn],t[maxn];

int lowbit(int x)            //树状数组求前缀和
{
    return x&(-x);
}

void update(int i,int x)
{
    while(i <= m)
    {
        t[i] += x;
        i += lowbit(i);
    }
}

int query(int x)
{
    int res = 0;
    while(x)
    {
        res += t[x];
        x -= lowbit(x);
    }
    return res;
}

signed main()
{   
    n = read();
    for(int i = 1; i <= n; i++) 
    {
        a[i] = read();
        b[i] = a[i];
    }
    sort(b+1,b+1+n);
    m = unique(b+1,b+1+n)-b-1;        //离散化
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(b+1,b+1+m,a[i])-b;
        int x = m-a[i]+1;                //反过来
        ans += (n-i+1)*query(x-1);
        update(x,i);
    }
    print(ans);
    putchar('\n');
    return 0;
}