bhupixb

Inversion counting using Merge Sort

Sep 23rd, 2019
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.13 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N = 65537 + 4;
  4. vector < long long > v(N);
  5. long long merge(int, int, int, int);
  6. long long merge_sort(int l, int r) {
  7. int mid = (l+r) >> 1;
  8. long long lInver = 0, rInver = 0, mergeInver = 0;
  9. if (l != mid) {
  10. lInver = merge_sort(l, mid);
  11. }
  12. if (r != mid+1) {
  13. rInver = merge_sort(mid+1, r);
  14. }
  15. if (r != l) {
  16. mergeInver = merge(l, mid, mid+1, r);
  17. }
  18. return mergeInver + lInver + rInver;
  19. }
  20.  
  21. long long merge(int l1, int r1, int l2, int r2) {
  22. vector < long long > temp(r2-l1+1);
  23. long long tInver = 0;
  24. int i = l1, j = l2, k = 0;
  25. while (i <= r1 && j <= r2) {
  26. if (v[i] <= v[j]) {
  27. temp[k] = v[i];
  28. ++i;
  29. }
  30. else {
  31. temp[k] = v[j];
  32. ++j;
  33. tInver += l2 - i;
  34. }
  35. ++k;
  36. }
  37. while (i <= r1) {
  38. temp[k++] = v[i++];
  39. }
  40. while (j <= r2) {
  41. temp[k++] = v[j++];
  42. }
  43. for (int k = 0, i = l1; i <= r2; ++i) {
  44. v[i] = temp[k++];
  45. }
  46. return tInver;
  47. }
  48.  
  49. int main() {
  50. int t = 1;
  51. // cin >> t;
  52. while (t--) {
  53. int n;
  54. cin >> n;
  55. // n = 1e7;
  56. for (int i = 0; i < n; ++i) {
  57. cin >> v[i];
  58. }
  59. cout << merge_sort(0, n-1) << '\n';
  60. }
  61. }
Add Comment
Please, Sign In to add comment