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
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | adamant | 155 |
4 | cry | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
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
Name |
---|
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.