如下图，第\(i\)行\(j\)列表示第\(j\)个数结尾，向前长度为\(i\)的逆序子序列个数。
递推方式见下图。
- 第一行全为\(1\)。
- 要填第\(2\)行的值，就往前找所有\(>\)当前元素的位置，把它们第\(1\)行的值加起来。
- 要填第\(3\)行的值，就往前找所有\(>\)当前元素的位置，把它们第\(2\)行的值加起来。
最终第\(3\)行值的和就是我们要求的结果。
怎么快速找出\(>\)当前元素的答案和呢？我们可以用线段树（树状数组）。发现数据范围太大，需要离散化。
线段树/树状数组需要维护第\(1\)行和第\(2\)行，第\(3\)行不参与运算，现求现加即可。
这里用线段树实现，注意开long long。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define lc (x<<1)
#define rc (x<<1|1)
#define N 1000010
using namespace std;
int n,a[N],b[N];
int sum[2][4*N];
int ans=0;
void update(int x){
sum[0][x]=sum[0][lc]+sum[0][rc];
sum[1][x]=sum[1][lc]+sum[1][rc];
}
void build(int l,int r,int x){
if(l==r){
sum[0][x]=sum[1][x]=0;
return;
}
int mid=(l+r)>>1;
build(l,mid,lc);
build(mid+1,r,rc);
update(x);
}
void change(int a,int v1,int v2,int l,int r,int x){
if(l==r){
sum[0][x]+=v1,sum[1][x]+=v2;
return;
}
int mid=(l+r)>>1;
if(a<=mid) change(a,v1,v2,l,mid,lc);
else change(a,v1,v2,mid+1,r,rc);
update(x);
}
pair<int,int> query(int a,int b,int l,int r,int x){
if(a<=l&&r<=b) return {sum[0][x],sum[1][x]};
int mid=(l+r)>>1;
pair<int,int> ans;
if(a<=mid){
auto t=query(a,b,l,mid,lc);
ans.first+=t.first,ans.second+=t.second;
}
if(b>mid){
auto t=query(a,b,mid+1,r,rc);
ans.first+=t.first,ans.second+=t.second;
}
return ans;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
int tn=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+tn,a[i])-b;
build(1,n,1);
for(int i=1;i<=n;i++){
auto q=query(a[i]+1,tn,1,n,1);
//q.first表示第1行的和
//q.second表示第2行的和
change(a[i],1,q.first,1,n,1);
ans+=q.second;
}
cout<<ans;
return 0;
}