1 #include <iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<vector> 6 #include<map> 7 using namespace std; 8 #define INF 0x7fffffff 9 #define MOD 100000000710 11 12 #define N 10001013 #define MAX 100010014 15 int C[MAX], S[MAX], b[N],d[N];16 long long f[N];17 long long total[N], ans;18 int num[N], T, s, t, i, j;19 20 int Lowbit(int x){21     return x&(x^(x-1));22 }23 24 void add(int pos,int num,int *P) {25     while(pos <= MAX) {26         P[pos] += num;27         pos += Lowbit(pos);28     }29 }30 31 int Sum(int end,int *P) {32     int cnt = 0;33     while(end > 0) {34         cnt += P[end];35         end -= Lowbit(end);36     }37     return cnt;38 }39 40 void init(){41     total[0] = 0;42     for(i = 1; i < N; ++i){43         total[i] = total[i-1] + i;44     }45 }46 47 int main() {48     //init();49     int t;50     cin>>t;51 52     while(t--) {53 54         scanf("%d",&T);55 56         memset(C,0,sizeof(C));57         memset(S,0,sizeof(S));58         memset(b,0,sizeof b);59         memset( d,0,sizeof d);60         memset(f,0,sizeof f);61         memset(num,0,sizeof num);62         //memset(num,0,sizeof(num));63         //memset(b,0,sizeof(b));64         //ans = 0;65         for(j = 0; j < T; j ++) {//因为第一个数前面比它小的数没有，所以j要从0开始66             scanf("%d",&num[j]);67             add(num[j]+1,1,C);68             b[j] = Sum(num[j], C);//Sum(num[j],C)求的就是小于s的个数，j - Sum(num[j],C)就是前j个数中大于num[j]的个数69             //printf("%d ",b[j]);70         }71         //printf("\n");72         //ans = 0;73         for(j = T-1; j > -1; --j){//反过来求第j个数右边中大于它的数的个数。74             add(num[j]+1 ,1, S);75             d[j] =T-1-j-Sum(num[j] ,S);//Sum(num[j],S)求的就是小于num[j]的个数76             //b[j] -= Sum(num[j]+1,S) - Sum(num[j],S)-1;77             //printf("%d ",b[j]);78             //ans += total[b[j]];79         }80         f[T-1]=0;81        for(int j=T-2;j>=0;j--)82         f[j]=d[j+1]+f[j+1];83        long long int res=0;84        for(int j=0;j<T;j++)85         res+=b[j]*f[j];86        cout<<res<<endl;87 88     }89     return 0;90 }91 92 代码君