dario-dsa's blog

By dario-dsa, 11 years ago, In English

Hi, can anyone help me with this task http://www.spoj.com/problems/INVCNT/ . First I try to think in BIT-way but I can't. Can anyone explain the solution of this task with BIT. BIT- Binary indexed tree

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The idea is to scan the array from left to right: when you are considering vi you should count how many elements vj (with j < i) are there such that vi < vj (in other words you should count how many elements, greater than the current element, you have already seen).

Using a BIT, you can keep how many times each possible value has appeared in the array. In this way you can easily retrieve how many numbers are there in some values range. So, if you are cosidering a generic element vi, first you should increment the answer opportunely, then you should update the BIT, because you have seen vi one more time than before.