A.K.Goharshady's blog

By A.K.Goharshady, 7 years ago, In English,
This one can be solved in O(nlgn) using a segment tree.
First we convert all powers to numbers in range 0..n-1 to avoid working with segments as large as 109 in our segment tree. Then for each of the men we should find number of men who are placed before him and have more power let's call this gr[j]. When ever we reach a man with power x we add the segment [0,x-1] to our segment tree , so finding gr[j] can be done by querying power of j in our segment tree when it's updated by all j-1 preceding men.
Now let's call number of men who are standing after j but are weaker than j as le[j]. These values can be found using the same method with a segment-tree or in O(n) time using direct arithmetic:
le[j]=(power of j -1)-(i-1-gr[j])
note that powers are in range 0..n-1 now.
Now we can count all triplets i,j,k which have j as their second index. This is le[j]*gr[j]
so the final answer is 

( \sum_{j=0}^{n-1} le[j]\times gr[j] )
 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why didnt you write tutorial in "all-in-one" post? Anyway, tutorial is written good! Thanks
7 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it
I wrote in 5 different posts , because some people want to read the tutorial of only one problem and want to solve other problems on their own
  • 7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    That's why it'll be great if a Spoiler will appear here. :-)
  • 7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks a lot for your turoial!
    I do not understand the meaning of le[j]=(power of j -1)-(i-1-gr[j]). Could you explain it? Thanks a lot.
    • 7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      We want to find number of men after j who are weaker. We know number of men before j , and we know number of stronger men before j , so we can easily find number of weaker men standing before j. 
      As we know number of all men who are weaker than j , we can find number of those who are weaker and are placed after j with a subtracting what we just found.
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is implementation of segement tree really tough?

7 years ago, # |
  Vote: I like it +1 Vote: I do not like it
can anyone clearly explain how to do this using BIT

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can this be done using merge sort ...

like inverse counting problem?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. For each index i, you can first find number of all inversions that have i as their first element and then all those that have i as their second element. Then just multiply them to find number of three-inversions (j,i,k) with i as their middle element.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the meaning of this line "we add the segment [0,x-1] to our segment tree".

An example would be very helpful.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

my solution using merge sort algo to find inversions. http://codeforces.com/contest/61/submission/33820916

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

    For the second time of inversion counting, I got the gist of what you are doing, namely, finding for each element, the number of inversions in which it is occurring as the first element. Please can you elaborate more on the thought process behind the processing you have done before you invoke the inversion count the second time?

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

In the year 2018, we have new-age technology that makes this problem fairly trivial to solve: Policy-based data structures. Specifically, order statistics trees. We can query them directly to find the number of elements less than x. So none of that coordinate compression/segment tree nonsense needed! See my solution here: http://codeforces.com/contest/61/submission/40569977

See here for more information regarding the data structure: https://codeforces.com/blog/entry/11080