//对于数列中的一个数，，在它前面比它大的一定要和它交换//在它后面比它小的一定得和它交换//可以用树状数组存入每一个数在它之前比它小的数的个数//那么(i-1)-total[i]为在它前面比它大的数的个数//然后在所有数都存入树状数组后用getsum(num[i])可以求出整个数列中比这个数小的数的个数//那么getsum(num[i])-1-total[i]则为在它之后比它小的数的个数//ans+=num[i]*(i-2+getsum(num[i])-2*total[i]);#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn=100010;__int64 total[maxn];int tree[maxn];int num[maxn];int lowbit(int i){ return (i&(-i));}int getsum(int i){ int sum=0; while(i>0) { sum+=tree[i]; i-=lowbit(i); } return sum;}void update(int i,int dx){ while(i<maxn) { tree[i]+=dx; i+=lowbit(i); }}int main(){ int n; while(scanf("%d",&n)!=EOF) { int a;int i; __int64 ans=0; memset(tree,0,sizeof(tree)); for(i=1;i<=n;i++) { scanf("%d",&a); num[i]=a; total[i]=getsum(a); update(a,1); } for(i=1;i<=n;i++) { ans+=num[i]*(i-2+getsum(num[i])-2*total[i]); } printf("%I64d\n",ans); } return 0;}
缘是浪漫的相遇，瞬间让你我的心化为永恒！
