CF61E Enemy is weak
如下图，第\(i\)行\(j\)列表示第\(j\)个数结尾，向前长度为\(i\)的逆序子序列个数。
递推方式见下图。
- 第一行全为\(1\)。
- 要填第\(2\)行的值，就往前找所有\(>\)当前元素的位置，把它们第\(1\)行的值加起来。
- 要填第\(3\)行的值，就往前找所有\(>\)当前元素的位置，把它们第\(2\)行的值加起来。
最终第\(3\)行值的和就是我们要求的结果。
怎么快速找出\(>\)当前元素的答案和呢？我们可以用线段树（树状数组）。发现数据范围太大，需要离散化。
线段树/树状数组需要维护第\(1\)行和第\(2\)行，第\(3\)行不参与运算，现求现加即可。
这里用线段树实现。
点击查看代码
#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;
}
