链接：Miku
----------------------
对于这个题，我们对于每一个数i，分别求出所有比它小的，在它前面的和
比它大的，在它后面的，然后把这两个乘起来，然后再把这些积加起来就可以了
-----------------------
然而这样直接做复杂度太高了，我们要优化，仿照树状数组求逆序对的方法，我们就可以在可以接受的时间内求出并且解决问题了
------------------------
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n; int a[30005]; int tree[30005]; int b[30005]; long long minn[30005]; long long ans; bool cmp(const int &x,const int &y){//要考虑数字相同的情况 if(a[x]!=a[y]) return a[x]<a[y]; else return x>y; } int lowbit(int x){ return x&-x; } void add(int x,int k){ while(x<=n){ tree[x]+=k; x+=lowbit(x); } return ; } int sum(int x){ int ans=0; while(x){ ans+=tree[x]; x-=lowbit(x); } return ans; } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&a[i]); b[i]=i; } sort(b+1,b+1+n,cmp); for(int i=1;i<=n;++i){//求比它小的 add(b[i],1); minn[b[i]]=sum(b[i]-1); } memset(tree,0,sizeof(tree)); for(int i=n;i>=1;--i){//倒着求，就是大的 add(b[i],1); minn[b[i]]*=sum(n)-sum(b[i]);//直接乘骑来 } for(int i=1;i<=n;++i){ ans+=minn[i]; } printf("%lld",ans); return 0; }
原文：https://www.cnblogs.com/For-Miku/p/12313174.html
