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 ith 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.
Input
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 Xth element of the sequence is Y and that you should count the number of inversions in the modified sequence.
Output
Output must contain M lines, the ith line of output containg the number of inversions in the sequence after the first i operations.
Example
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
hide comments
agrawal117:
20190713 21:21:54
@Aman Shrivastava>> integers between 1 and 50000 

mamnoonsiam:
20170621 16:37:29
Solved in one go ... works O(n^2) code :')


seyedssz:
20170501 09:32:30
Using segment wiht each node a BIT >


Dipjal:
20170316 01:07:24
At single go! :D 

bicsi:
20150502 16:55:32
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: 20150502 16:56:10 

Naman Taneja:
20150112 21:05:14
Nice Question ! A little optimization is required Last edit: 20150114 21:26:59 

Archit Jain:
20140914 14:42:42
segment tree giving tle?


Aman Shrivastava:
20140913 06:19:18
limits of Ai??? Last edit: 20140913 06:19:31 
Added by:  Gogu 
Date:  20060531 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource: 