思路详解参见:http://blog.sina.com.cn/s/blog_691ce2b70101lolv.html
这里用树状数组实现,时间要快很多。
//0 KB 113 ms #include <stdio.h> #include <string.h> #define lowbit(x) (x &(-x)) const int M = 100005; const int N = 20005; int ar[M],val[N],lmin[N],rmin[N]; void add (int x) { while (x <= M) ar[x] += 1,x += lowbit(x); } int sum(int x) { int res = 0; while (x > 0) res += ar[x],x -= lowbit(x); return res; } int main () { int T,n,i; scanf ("%d",&T); while (T--) { scanf ("%d",&n); memset (ar,0,sizeof(ar)); for (i = 1;i <= n;i ++) { scanf ("%d",&val[i]); add(val[i]); lmin[i] = sum(val[i]-1); } memset (ar,0,sizeof(ar)); for (i = n;i >= 1;i --) { add(val[i]); rmin[i] = sum(val[i]-1); } //for (i = 1;i <= n;i ++) // printf ("%d %d\n",lmin[i],rmin[i]); long long ans = 0; for (i = 1;i <= n;i ++) ans += lmin[i]*(n-i-rmin[i])+(i-lmin[i]-1)*rmin[i]; printf ("%lld\n",ans); } return 0; }