CODEWITHSUNDEEP
c++algorithmfenwick-tree
Dario
Dario

Reputation: 115

SPOJ INVCNT - how?

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 c++

Upvotes: 4

Views: 2573

Answers (1)

IVlad
IVlad

Reputation: 43487

Assuming you know how to solve the following problem in O(log n) per query and update using a BIT:

Given an array A[1 .. n], implement the following functions efficiently:
query(x, y) = return A[x] + A[x+1] + ... + A[y]
update(x, v) = set A[x] = v

You can solve your current problem like this: first, normalize your array values. This means that you must transform all of your values such that they are in the interval [1, n]. You can do this with a sort. For example, 5, 2, 8 will become 2, 1, 3. (Note: 1, 2, 3 are indexes in the sorted order of 5, 2, 8)

Then, for each i, we will answer how many inversions A[i] generates with elements j < i. For this, we need to find the number of elements before i that are larger than i. This is equivalent to query(A[i] + 1, n).

After this query, we do update(A[i], 1).

Here's how this works: our BIT array will initially be filled with zeros. A 1 at position k in this array means that we have encountered the value k in our iterating over the given array. By calling query(A[i] + 1, n), we find how many inversions A[i] generates with elements before it, because we query how many elements larger than it we have iterated over so far.

After finding this, we need to mark A[i] as visited. We do this by updating the position A[i] in our BIT array and putting a 1 at it: update(A[i], 1).

Since the numbers in the array are distinct from 1 to n, your BIT array has size n and the complexities are logarithmic in n.

Write if you want details on how to solve the initial problem, although it is a classic and you should be able to easily find code on Google.

Note: the problem also has a nifty solution using merge sort that you might want to think about.

Upvotes: 6

Related Questions