题意:给出长度为n的序列a,求序列a所有区间的逆序数之和?
逆序数(ia[j] 则(i,j)为一个逆序数对). n<=1e6,a[i]<=1e9.

ia[j] (i,j) 这一对 出现了 i*(n-j+1)次.算贡献
一对对算是也有n^2对 那么从后往前枚举左端点i 用BIT统计[i+1,n]比a[i]小的权值即可 a[i]>a[j] 则累加上n-j+1.

答案爆ll,这里用了__int128

#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int N=1e6+5;
int n,a[N];
ll c[N*2]; 
vector<int> b;
int getid(int x)
{
    return lower_bound(b.begin(),b.end(),x)-b.begin()+1;
}
int lowbit(int x)
{
    return x&-x;
}
void update(int x,ll val)
{
    for(int i=x;i<=n;i+=lowbit(i))
        c[i]+=val;  
} 
ll query(int x)
{
    ll res=0;
    for(int i=x;i>0;i-=lowbit(i))
        res+=c[i];
    return res; 
} 
vector<int> aa;
void output(__int128 v){
    if(v==0)puts("0");
    else{
        while(v){
            aa.push_back(v%10);
            v/=10;
        }
        reverse(aa.begin(),aa.end());
        for(auto it:aa)printf("%d",it);puts("");
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),b.push_back(a[i]);
    sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    ll ans=0;
    for(ll i=n;i>=1;i--)
    {
        int pos=getid(a[i]);
        ll sj=query(pos-1);
        ans+=i*sj; 
        update(pos,n-i+1);
    }
    output(ans);
    return 0;
}