Difficulty in understanding the approach for solving Spoj DQuery

Question

I was trying to solve this problem on SPOJ: http://www.spoj.com/problems/DQUERY/

But after a few hours of trying to solve it, I googled for a possible hint. I found one approach described here: http://apps.topcoder.com/forums/;jsessionid=5A69961AF7DF7FBB00FDFE13B80B5D2E?module=Thread&threadID=627423&start=0&mc=13

But I am not able to understand it properly. Can anybody help me in understanding the approach.

Answer 1

The result of a query [a, b] is number of integers whose last occurrence in [1, b] is >= a.

Suppose that we have query (2;4) for sequence from the example: [1, 1, 2, 1, 3]. To make a set from a multiset [1, 2, 1] we can count last positions of numbers from 1 to b and choose only these that are >= a. So these occurences in this example are: 4 (for 1) and 3 (for 2). Both of them are >= 2 = a so the result is 2.

How to efficiently store all of the last occurences and be able to quickly find all of them which are >= a? In a tree (interval tree or segmented tree). I'd use BIT (Binary Indexed Tree aka Fenwick Tree) described here.

But first we have to put events in order. What events? An event is either a number on a certain position (so a pair (x;y) where x is a number and y is a position) - NumberEvent - or an interval (a pair (a;b)) - QueryEvent. We have to sort our queries. First we should consider numbers as without adding them to the tree queries would have no sense. So we want to start with the first position (so we sort NumberEvents by positions - y). On the first position there is 1. We remember that last_position1 = 1 and we add position 1 to the tree. Next we have 1 on position 2. We check last_position1 and it's not empty so we remove position 1 from the tree, add position 2 to the tree and update last_position1 = 2. Next we have 2 on position 3. We check last_position2 and it's empty, so we have last_position2 = 3 and we add 3 to the tree. Next we have 1 on position 4. We remove position 2 from the tree, add 4 and update last_position1 = 4. And now something different. We see that we have a query with b=4 and we considered all numbers from positions [1;b]. The only thing left is that we count positions in the tree that are >= a=2. There are 2 of them: 3, 4. We remember that for (2;4) the result is 2 (we have to print it in good order, so instead of (2;4) I'd remember the query as (2;4;2) as it was the second query and in the end I'd print all queries from 1 to q). And that's it. Therefore, the sorted queries are:

1 1 NumberEvent [number;position]
1 2 NumberEvent
2 3 NumberEvent
1 4 NumberEvent
2 4 QueryEvent [a;b] or [i;j] from the task - sorted by b
3 5 NumberEvent
1 5 QueryEvent
3 5 QuertEvent

Sorting and joining all q+n queries takes (q+n)log(q+n) time. Then, for each q+n queries we use log(n) time (because there are at most n numbers in the tree). The overall complexity is then O((q+n)log(q+n)).

As for operations on a tree.

I'll base my description on this polish site. There are good images and codes.

Indexing: If we want to have interval tree for numbers from range 0..x we have to first round x up to the power of 2 subtracted by 1. So for x=5 we change x to 2^3-1=7. The intervals are like on the image from the link. E.g. for range 0..7 and for interval 4..5 it's index is 6 (we count from 1, not 0).

Adding/subtracting value: Suppose that we want to add to the tree with range 0..7 number 5. Interval's 5..5 index is 5+2^3=13 (as we have values from range 0..2^3-1). So we update tree[13]+=1 (first tree[] is all 0's). We move up, to the interval which includes 5..5 and it's 4..5 with index floor(13/2)=6 (check it on the picture from the link). We have to update it as well so we do tree[6]=tree[2*6=12]+tree[2*6+1=13]. Then: tree[6/2=3]=1, tree[3/2=1]=1 and then we have 1/2=0 so we stop (as I said - we count indexes from 1 so when we have 0 we get out of the loop). The time of adding a number is logaritmic (we divide by 2 the number each time). We can subtract a number from the tree the same way. Just subtract 1 instead of adding it.

Query: We can check how many numbers there are in the interval a..b also in logaritmic time. We are interested in numbers >=a so the result is query(max)-query(a-1). Max in our case equals n as the we keep positions in the tree and they are from range 1..n. So we are interested in query(n,a-1). How to calculate query? First add to n and a-1 number 2^3 (for range 1..x) to get intervals n..n and a-1..a-1. We then add tree[a] (where a=a-1) or tree[b] (where b=n) to the result while a!=b. If a%2=0 then a is the right child and we add it. Also b%2=1 then b is the left child. We are interested in left childs of b because otherwise they would be greater than b so they would be out of range. The same with a. Left children of a are out of range.

You can see the codes for query and insert in the link.

If you have any doubts - ask.