I_love_Leyeli_Meredova's blog

Please help with segment tree!
By I_love_Leyeli_Meredova, history, 3 months ago, In English

Hello everybody

Problem

Thank you!

  • UPD:

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't quite get it.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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 here

      the time complexity for my solution is $$$O(40 * N log N)$$$ which is passable.

      → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it
Hint 1
Hint2
→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I figured out how to solve the problem,

but
→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Use arrays instead of vectors should be easier. But, if you really want to implement it that way, you can use vector(45, 0).

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by I_love_Leyeli_Meredova (previous revision, new revision, compare).

→ Reply