C小加

    #include<cstdio>
    #include<iostream>
    using namespace std;
    const int MAXM=1000003;
    const int INF=0x7fffffff-1;
    long long cnt;
    int arr[MAXM];
    int temp1[MAXM/2+1], temp2[MAXM/2+1];
    // 歸并排序中的合并算法
     void Merge(int array[], int start, int mid, int end)
      {

         int n1, n2;
         n1 = mid - start + 1;
         n2 = end - mid;

         // 拷貝前半部分?jǐn)?shù)組
         for (int i = 0; i < n1; i++)
          {
             temp1[i] = array[start + i];
         }
         // 拷貝后半部分?jǐn)?shù)組
         for (int i = 0; i < n2; i++)
          {
             temp2[i] = array[mid + i + 1];
         }
         // 把后面的元素設(shè)置的很大
         temp1[n1] = temp2[n2] = INF;
         // 逐個(gè)掃描兩部分?jǐn)?shù)組然后放到相應(yīng)的位置去
         for (int k = start, i = 0, j = 0; k <= end; k++)
          {
             if (temp1[i] <= temp2[j])
              {
                 array[k] = temp1[i];
                 i++;
             }
             else
              {
                  cnt+=n1-i;//逆序?qū)Φ膫€(gè)數(shù)
                 array[k] = temp2[j];
                 j++;
             }
         }
     }

     // 歸并排序
     void MergeSort(int array[], int start, int end)
      {
         if (start < end)
          {
             int i;
             i = (end + start) / 2;
             // 對(duì)前半部分進(jìn)行排序
             MergeSort(array, start, i);
             // 對(duì)后半部分進(jìn)行排序
             MergeSort(array, i + 1, end);
             // 合并前后兩部分
             Merge(array, start, i, end);
         }
     }

     int main()
     {
         //freopen("in.txt","r",stdin);
        int t;
        scanf("%d",&t);
        while(t--)
        {
            cnt=0;

            int n;
            scanf("%d",&n);
            for(int i=0;i<n;i++)
            {
                scanf("%d",arr+i);
            }
            MergeSort(arr,0,n-1);
            printf("%lld\n",cnt);
        }
        return 0;
     }