题意:求所有子区间的逆序数对的个数。
思路
考虑贡献。假设存在逆序数对(a[i],a[j] (i<j)
那么含有a[i]的区间的左边界L<=i,含有a[j]的区间的右边界R>=j。
也就是逆序数对贡献的个数为i*(n-j+1)。
我们可以枚举j,统计在j前面,有多少个数比a[j]大,计算他们的下标之和。(满足a[i]>a[j] && i<j i的值就是左边界可以选取的个数)
他们能选取的右边界的个数就是n-i+1。
对于求前面比a[j]大的数的下标之和,可以用树状数组来统计。
只关注数的相对大小,不在乎具体值,注意离散化。
注意答案炸LL

#include<bits/stdc++.h>
using namespace std;
#define ll __int128
const int maxn=1e6+5;
ll c[maxn];
void add(ll x,ll k){
    for(;x<maxn;x+=x&-x) c[x]+=k;
}
ll sum(ll x){
    ll ans=0;
    for(;x;x-=x&-x) ans+=c[x];
    return ans;
}
void print(ll x){
    if(x<10){
       cout<<(int)(x%10);
        return ;
    }
    print(x/10);
    cout<<(int)(x%10);
}
int main(){
    int n;cin>>n;
    vector<int> a(n),b(n);
    for(int i=0;i<n;i++) cin>>a[i],b[i]=a[i];
    sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    __int128 ans=0;
    for(int i=0;i<n;i++){
        int pos=lower_bound(b.begin(),b.end(),a[i])-b.begin()+1;
        ans+=(ll)1*(sum(n)-sum(pos))*(n-i);
        add(pos,i+1);
    }
    print(ans);
    return 0;   
}