|
Yes, it can be solved with BIT. First compress the numbers(they can be up to 10^7 but their count is at most 200000). You go through each number in the permutation. You insert 1 in the BIT at the corresponding position(if the number is 3, insert 1 at the third position). The freshly inserted number gives query(num + 1, N) inversions.
Let's take the first example - 3, 1, 2. At the beginning the BIT is 0, 0, 0. After inserting 3 the BIT is 0, 0, 1. After inserting 1 the BIT is 1, 0, 1 which gives 1 inversion. After inserting 2, the BIT is 1, 1, 1 which gives again 1 inversion. 1 + 1 = 2 total inversions.
Let's take the second example - 2, 3, 8, 6, 1. BIT - 0, 0, 0, 0, 0, 0, 0, 0. Insert 2: BIT - 0, 1, 0, 0, 0, 0, 0, 0. Insert 3: BIT - 0, 1, 1, 0, 0, 0, 0, 0. Insert 8: BIT - 0, 1, 1, 0, 0, 0, 0, 1. Insert 6: +1 inversions BIT - 0, 1, 1, 0, 0, 1, 0, 1. Insert 1: + 4 inversions BIT - 1, 1, 1, 0, 0, 1, 0, 1.
P.S. In the examples I haven't included the compression for clarity. |