### I_love_Leyeli_Meredova's blog

By I_love_Leyeli_Meredova, history, 7 weeks ago,

Hello everybody

Problem

Thank you!

• UPD:

 » 7 weeks ago, # |   +3 Hi, I'm not at home right now, so I am unable to implement it. I think the intended solution is to use the fact that a[i] is small. This inspires us to make each node have an array of size 40, to store the number of occurrences of each number. Then merging nodes is just counting the inversion number of the two arrays + inversion number of left array + inversion number of right array.
•  » » 7 weeks ago, # ^ |   0 I didn't quite get it.
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 Hmmm, you can try understanding a node in the segment tree contains the information of all the numbers in the segment. When we want to combine two nodes, lets call them L and R, inversion of current node = inversion of L + inversion of R + inversion of array of (L, R). In order to do that, we can maintain a frequency table in each of the node (size 40). Also notice that it is better that we count that with a prefix sum in 40 operations, instead of doing a 40 * 40 operation (looping through i, j).After merging the nodes, we still notice that our answer can't just simply sum all together, because the segment tree considers separated segments. But we can observe that the number of segments is around log N, so we can simply brute force them together to calculate the answer.Code link herethe time complexity for my solution is $O(40 * N log N)$ which is passable.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 thanks!=)
 » 7 weeks ago, # |   0 Hint 1Store frequency of elements in the range + count of inversion in the range Hint2For combining brute for both ranges using frequencycombine — ans=inversion in left range + inversion in right range + inversion across range.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 thanks, I will try to solve it
 » 7 weeks ago, # |   0 I think the idea is to use merge sort tree. If you don't know about it, then it's a special kind of segment tree with array/map/st/multiset stored in each node representing the count of each element in the range
 » 7 weeks ago, # | ← Rev. 2 →   0 I figured out how to solve the problem, butvector(and I need the array size to be 40)> tree;tree.assign(2*size, ????)what do I need to write where is the question mark? and I need the array size to be 40
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Use arrays instead of vectors should be easier. But, if you really want to implement it that way, you can use vector(45, 0).
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by I_love_Leyeli_Meredova (previous revision, new revision, compare).