题意

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

解题思路

树状数组+离散化
先考虑简单的问题，如果是单独求逆序对，即离散化之后，边往树状数组中插元素边统计逆序对
该题要统计所有区间的逆序对
首先考虑如果一对元素....ai....aj...构成逆序对会为结果贡献多少个逆序对？
当然是包含ai，aj的子区间的个数
在ai前面有i-1 个元素，aj后面有n-j个元素，即子区间个数为i（n-j+1）个
接下来列举几个例子试一下发现，如果ai，ak都与aj构成逆序对，那么结果为i（n-j+1）+k（n-j+1）=(i+k)(n-j+1)
显然我们发现可以离散化后，用树状数组维护每个数的下标之和
但这样居然还不够！！！
这个题，他，答案爆long long
可以选择用__int128

AC代码

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define maxn 1000010
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int MOD=1000000007;
const double pi=acos(-1.0);
inline int lowbit(int x){ return x&(-x);}
struct node{
    ll val,k;
}a[maxn];
ll c[maxn],n,lsh[maxn]; //c为树状数组，lsh为离散化数组
bool cmp(node a,node b){
    return a.val>b.val;
}
void add(int k,int x){
    for(int i=k;i<=n;i+=lowbit(i)) c[i]+=x;
}
ll sum(int x){
    ll ans=0;
    for(int i=x;i>0;i-=lowbit(i)) ans+=c[i];
    return ans;
}
int main()
{
    io;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].val; a[i].k=i;
    }
    sort(a+1,a+n+1,cmp);
    int cnt=0;
    a[0].val=inf; //因为数组元素可以取0，将a[0]设为无法取到的值
    //离散化
    for(int i=1;i<=n;i++){
        if(a[i].val!=a[i-1].val) lsh[a[i].k]=++cnt;
        else lsh[a[i].k]=cnt;
    }
    __int128 ans=0,tmp;
    for(int i=1;i<=n;i++){
        add(lsh[i],i);
        tmp=sum(lsh[i]-1);
        ans+=tmp*(n-i+1);
    }
    if(ans==0) cout<<0<<endl;
    else{
        //__int128无法用cout输出，转化为字符串（感觉好笨拙）
        string s;
        while(ans!=0){
            s+=(ans%10)+'0';
            ans/=10;
        }
        for(int i=s.size()-1;i>=0;i--) cout<<s[i];
    }
    return 0;
}