aishraj · November 13, 2011 09:59 · Oct 13, 2011
diff --git a/Hint.md b/Hint.md
@@ -0,0 +1 @@
+The answer is the number of inversions in the array, which is the number of pairs i,j such that i < j and a[i] > a[j]. Counting this is a fairly classical problem with many solutions such as using data structures such as Balanced Trees or Binary Indexed Trees. Another particularly elegant solution involves modifying merge sort to count the number of inversions when merging the two sorted halves in the algorithm.
diff --git a/problemsetter.cpp b/problemsetter.cpp
@@ -0,0 +1,26 @@
+#include<iostream>
+#include<stdio.h>
+#include<string.h>
+using namespace std ;
+#define MAXN 100002
+#define MAX 1000002
+int n,a[MAXN],c[MAX] ;
+int main()
+{
+ int runs ;
+ scanf("%d",&runs) ;
+ while(runs--)
+ {
+  scanf("%d",&n) ;
+  for(int i = 0;i < n;i++) scanf("%d",&a[i]) ;
+  long long ret = 1LL * n * (n - 1) / 2 ;
+  memset(c,0,sizeof c) ;
+  for(int i = 0;i < n;i++)
+  {
+   for(int j = a[i];j > 0;j -= j & -j) ret -= c[j] ;
+   for(int j = a[i];j < MAX;j += j & -j) c[j]++ ;  
+  }
+  cout << ret << endl ;
+ }
+ return 0 ;
+}
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		The answer is the number of inversions in the array, which is the number of pairs i,j such that i < j and a[i] > a[j]. Counting this is a fairly classical problem with many solutions such as using data structures such as Balanced Trees or Binary Indexed Trees. Another particularly elegant solution involves modifying merge sort to count the number of inversions when merging the two sorted halves in the algorithm.
No results found