• Source 
    1. #include<cstdio>
    2. #include<iostream>
    3. #include<cstring>
    4. #define INF 0x3f3f3f3f
    5.  
    6. using namespace std;
    7.  
    8. long long arr[500005],swp;
    9.  
    10. long long L[250005];
    11.  
    12. long long R[250005];
    13.  
    14. void Merge(long long p,long long q,long long r)
    15. {
    16.  
    17.     long long i,j,k,n1,n2;
    18.  
    19.     n1 = q-p+1;
    20.  
    21.     n2 = r-q;
    22.  
    23.  
    24.     for(i=1; i<=n1; i++)
    25.         L[i]=arr[p+i-1];
    26.  
    27.     for(i=1; i<=n2; i++)
    28.         R[i]=arr[q+i];
    29.  
    30.  
    31.     L[n1+1]=INF;
    32.  
    33.     R[n2+1]=INF;
    34.  
    35.     i=j=1;
    36.  
    37.  
    38.     for(k=p; k<=r; k++)
    39.     {
    40.         if(L[i]<=R[j])
    41.         {
    42.             arr[k]=L[i];
    43.             i++;
    44.         }
    45.         else
    46.         {
    47.             arr[k]=R[j];
    48.  
    49.             swp+=(n1-i+1);
    50.  
    51.             j++;
    52.         }
    53.     }
    54. }
    55.  
    56. void merge_sort(long long p,long long r)
    57. {
    58.  
    59.     long long q;
    60.  
    61.  
    62.     if(p<r)
    63.     {
    64.         q=(p+r) /2;
    65.  
    66.         merge_sort(p,q);
    67.  
    68.         merge_sort(q+1,r);
    69.  
    70.         Merge(p,q,r);
    71.     }
    72. }
    73.  
    74. int main()
    75. {
    76.     long long n,i;
    77.  
    78.     while(scanf("%lld",&n)&&n)
    79.     {
    80.         for(i=1; i<=n; i++)
    81.             scanf("%lld",&arr[i]);
    82.  
    83.             swp = 0;
    84.  
    85.         merge_sort(1,n);
    86.  
    87.         printf("%lld\n",swp);
    88.  
    89.         memset(arr,0,sizeof(arr));
    90.  
    91.     }
    92.  
    93.     return 0 ;
    94. }