DYNAINV - Editorial

general
, ,
21

@suryanit He used that fact that any swap operation will simply alter the parity of the no. of inversions. We can write a simple O(n) procedure to count the number of swaps required to sort the given permutation of 1-N, and then use this number to easily determine the final parity. The main insight here is that the no of inversions depends solely on the final order of elements, and not on the swaps which are used to get there.

@yash_15 Thanks for sharing this method!

22

@yash_15 sir how did you come up with such a fantastic solution, i could have never dreamt of thinking it on my own

23

@yash_15 How the overall effect is 2k+1 and not k+1 ?

24

Oh, this k has no relation with the other k . This was used to say that the number of inversions is odd (formally).

25

@rach8 please refer to my answer.

26

I actually already did O((N + Q)logn * log(max)) using segtree on trie or treap on trie but both gave TLE , idk why but O(NlogN + NrootNlogMax) worked faster.