So , formally the problem statement :
You are given a sequence A of N (N≤250000) integers between 1 and 50000. On this sequence you have to apply M (M≤10000) operations of the form: modify the i-th element in the sequence and then say how many inversions are there in the sequence. The number of inversions in a sequence is given by the number of pairs (i,j) with i < j and Ai > Aj.
My approach is to , 1) Divide the array into square root pieces , and maintain a fenwick tree for each of the blocks that stores 1 corresponding to each number in that block ( For querying number of numbers lesser than a particular value in that block )
2) Count the inversions .
3) Now whenever Update comes , I update get inversions from all blocks except the index's box(I count the difference between the inversions due to the new value — inversions due to old value and add it to the inversions) and add it ! Plus I traverse the block of index ! Total Query time O( Sqquare root of N * log 50000 ) .
It is giving TLE Even with fast scanning and outputting Here is my code , can it be further optimised ? Ideone
Link to problem Spoj
Is there any other approach to it ?