离散化 + 树状数组

先看一下一般求逆序数的思路：设置vis数组，表示数字在前面遍历过程中出现的次数；遍历数组，vis[ar[i]]加一，然后求出大于ar[i]的数在前面出现的次数并加入到ans中。
当序列数字过大是可以采用离散化处理，因为只需要知道大小关系即可，不必知道到底大了多少；对于求大于ar[i]的数出现的次数，可以采用树状数组求和：sum(vis[maxx]-vis[ar[i]])。

再回到本题，要求出所有区间的逆序数的总和，换一句话说就是求出所有逆序对所在区间数的总和。
当(i,j)为逆序对时，其对ans的贡献为i* (n-j+1)（考虑到树状数组，下标从1开始）。
当(i_1,j)(i_2,j)(i_3,j)...为逆序对时，其对ans的贡献为:i_1* (n-j+1)+i_2* (n-j+1)+i_3* (n-j+1)+...=sum(i)* (n-j+1)。其余步骤回到求逆序数的思路即可。

还有个小问题，最后输出的值会爆long long（活久见。。。），可用__int128解决。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
#define fir first
#define sec second
using namespace std;

typedef __int128 ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=1e6+9;
const ll maxx=1e12+9;

int n,ar[maxn];
P tmp[maxn];
ll d[maxn];

void Print(ll x)
{
    if(!x) return;
    Print(x/10);
    printf("%d",x%10);
}
ll sum(int p)
{
    ll res=0;
    while(p) res+=d[p],p-=(p&(-p));
    return res;
}
void add(int p,int t)
{
    while(p<=n) d[p]+=t,p+=(p&(-p));
}
void init()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&ar[i]),ar[i]++,tmp[i].fir=ar[i],tmp[i].sec=i;
    sort(tmp+1,tmp+n+1);
    int cnt=2;
    ar[tmp[1].sec]=1;
    for(int i=2;i<=n;i++)
    {
        if(tmp[i].fir==tmp[i-1].fir) ar[tmp[i].sec]=ar[tmp[i-1].sec];
        else ar[tmp[i].sec]=cnt++;
    }
}
int main()
{
    init();
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ll t=n-i+1;
        ans+=(sum(n)-sum(ar[i]))*t;
        add(ar[i],i);
    }
    if(ans==0) printf("0");
    else Print(ans);
}