how to solve the problem without modulo 2 in O(logn) per query ? i solved it in (NlogN + QrootNlogN) , is anything better possile ?
I think you can do it @rajat1603 . Instead of breaking upinto pieces try maintaining Fenwick trees starting at position i such that they span upto 2^j , then you can achieve something log N * log N I guess!!
Read Sparse Table on Topcoder , My idea is very similar to that , wherever we can break into square root pieces , we have a very high probability that we can do it like the sparse table!
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.
https://www.codechef.com/viewsolution/7948758
This is my solution which gives WA. Can anyone identify the mistake?
Can somebody please tell what’s wrong with my answer , its showing WA in the last two tasks.I have used enhanced merge sort to count the number of inversions and used the fact that parity changes after every swap.
https://www.codechef.com/viewsolution/8959784