SWAPS - Counting inversions
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.
The first line of input contains the number N and the next line contains the numbers that form the sequence. After that follows the number M and then M lines, each containig 2 integers X and Y, meaning that new value of the X-th element of the sequence is Y and that you should count the number of inversions in the modified sequence.
Output must contain M lines, the i-th line of output containg the number of inversions in the sequence after the first i operations.
Input: 10 2 6 6 4 7 6 3 5 9 1 7 8 8 5 1 5 6 10 5 7 1 10 10 4 6 Output: 17 18 16 13 14 8 6
At single go! :D
Solved using sqrt(n) - length sequence preprocessing and fast read ^_^! Even though my complexity was (I think) worse than it should have been ( O( sqrt(n) * log(50000) ) per query ), it seemed to go rather well in practice (0.96 on time). Is there a solution in O(log(n)) per query?Last edit: 2015-05-02 16:56:10
Nice Question ! A little optimization is requiredLast edit: 2015-01-14 21:26:59
segment tree giving tle?
limits of Ai???Last edit: 2014-09-13 06:19:31