求出每个位置左边有几个比它大，右边有几个比它小，然后乘法原理加起来就够了。
大于小于什么的用树状数组YY一下就出来了。
#include #include #include #include #include #include using namespace std; int n; int c[2000000]; struct node { int x; int id; }a[2000000]; bool cmp(node x,node y) { return x.x 0) { sum+=c[n]; n=n-lowbit(n); } return sum; } void change(int i,int x) { while(i<=n) { c[i]=c[i]+x; i=i+lowbit(i); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i].x); a[i].id=i; } sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) mp[a[i].id]=i; for(int i=1;i<=n;i++) { change(mp[i],1); ls[mp[i]]=Sum(mp[i])-1; lb[mp[i]]=i-ls[mp[i]]-1; } long long ans=0; // for(int i=1;i<=n;i++) // { // printf("%d ",lb[mp[i]]); // } // puts(""); // for(int i=1;i<=n;i++) // { // printf("%d ",ls[mp[i]]); // } for(int i=1;i<=n;i++) { rs[mp[i]]=(mp[i]-1-ls[mp[i]]); ans+=rs[mp[i]]*lb[mp[i]]; } cout<