no all these data structure also take time O(nlogn)
solving this problem using segment tree
map all elements to its index on the sorted array.
ex. 2 3 8 6 1 --> 1 2 4 3 0
intialiize all element in segment tree wid zero
start from the last index of array
whenever u visit a node increase its value by 1 --> one more value came in
this range
if u have go right child then increase the count by number of element in
left child(that is value left node). thats it;
void query(int a, int s, int e, int node, unsigned long long &count)
{
int mid = (s+e)>>1;
tree[node] += 1;
if (s == e) return;
if (a <= mid)
{
query(a, s, mid, (node<<1)+1, count);
}
else
{
count += tree[(node<<1)+1];
query(a, mid+1, e, (node<<1)+2, count);
}
return;
}
I have written another code using ur logic its giving correct answer. I m
not getting where u r wrong. :P
#include <stdio.h>
unsigned long long int merge_and_count (int *a, int start, int mid, int end)
{
int len_a = mid - start + 1;
int len_b = end - mid;
int C[end - start + 1];
int k = 0;
int i = start;
int j = mid + 1;
unsigned long long int count = 0;
int rem = len_a;
while ( i <= mid && j <= end ) {
C[k++] = a[i] < a[j] ? a[i] : a[j];
if ( a[j] <= a[i] ) {
count += rem;
j++;
} else {
i++;
rem--;
}
}
while ( i <= mid ) {
C[k++] = a[i++];
}
while ( j <= end ) {
C[k++] = a[j++];
}
for ( i = start; i <= end; i++ ) {
a[i] = C[i-start];
}
return count;
}
unsigned long long int sort_and_count(int *a, int start, int end)
{
int mid;
unsigned long long int rA, rB, r;
if ( end == start )
return 0;
else {
mid = (start + end) >> 1;
rA = sort_and_count (a, start, mid);
rB = sort_and_count (a, mid + 1, end);
r = merge_and_count (a, start, mid, end);
} return (rA+rB+r);
}
int main()
{
int t, n, i;
int a[200100];
scanf ("%d", &t);
while ( t-- ) {
scanf ("%d", &n);
for ( i = 0; i < n; i++ ) {
scanf ("%d", &a[i]);
}
printf ("%llu\n", sort_and_count(a, 0, n - 1));
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
