I'm having trouble at this problem on Vietnam SPOJ. The problem is: Given array a[1], a[2], ... a[n]
, count the number of pair (u, v)
that u < v
and a[u] > a[v]
. Constrain: n <= 60000
and a[i] <= 60000
.
I tried to this using Fenwick Tree. But I'm getting only 60 points (maximum points is 100). Is there anything wrong in my implementation?
t.add(n, a[i], 1); ---> t.add(60000, a[i], 1);
Oh, that was a stupid mistake. Thanks a lot!