Guest User

Inversion count

a guest
Jul 2nd, 2015
296
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. long long merge(long long arr[], long long temp[], long long left, long long mid, long long right)
  5. {
  6. long long i, j, k;
  7. long long inv_count = 0;
  8.  
  9. i = left;
  10. j = mid;
  11. k = left;
  12. while ((i <= mid - 1) && (j <= right))
  13. {
  14. if (arr[i] <= arr[j])
  15. {
  16. temp[k++] = arr[i++];
  17. }
  18. else
  19. {
  20. temp[k++] = arr[j++];
  21.  
  22.  
  23. inv_count = inv_count + (mid - i);
  24. }
  25. }
  26.  
  27.  
  28. while (i <= mid - 1)
  29. temp[k++] = arr[i++];
  30.  
  31.  
  32. while (j <= right)
  33. temp[k++] = arr[j++];
  34.  
  35.  
  36. for (i=left; i <= right; i++)
  37. arr[i] = temp[i];
  38.  
  39. return inv_count;
  40. }
  41.  
  42. long long mergeSort(long long arr[], long long temp[], long long left,long long right)
  43. {
  44. long long mid, inv_count = 0;
  45. if (right > left)
  46. {
  47.  
  48. mid = (right + left)/2;
  49.  
  50.  
  51. inv_count = mergeSort(arr, temp, left, mid);
  52. inv_count += mergeSort(arr, temp, mid+1, right);
  53.  
  54.  
  55. inv_count += merge(arr, temp, left, mid+1, right);
  56. }
  57. return inv_count;
  58. }
  59.  
  60.  
  61.  
  62. int main()
  63. {
  64. int t;
  65. scanf("%d",&t);
  66. long n;
  67. while(t--)
  68. {
  69. scanf("%ld",&n);
  70. long long a[n],temp[n],i,j;
  71. for(i=0;i<n;i++){
  72. scanf("%lld",&a[i]);
  73. temp[i]=0;
  74. }
  75. long long count=mergeSort(a,temp,0,n-1);
  76.  
  77. printf("%lld\n",count);
  78. }
  79. return 0;
  80. }
RAW Paste Data