hello everyone,
Recently i came across this problem http://www.spoj.com/problems/DQUERY/en/. I coded the offline solution, but i was wondering how to solve it using persisent segment trees.I kept an array last_occur[i] which stores the latest occurence of the number i. now given a range (l,r) we need to find number of distinct elements with last_occur[i] < l.I got stuck here, how do we solve this part?
What is the problem with doing persistent. We can make seg tree for the last occurunence till r. Now seg tree for last occurence till r+1 will need atmost two updates from previous one . so 2*logn nodes. Now we have built persistent seg tree. we can for query (l,r) do sum query on seg tree of root r.
Suppose lst[i] is the last occurence of a[i], where lst[i] < i.
Now sort the array in increasing order of lst[i] , keeping the initial index, and then iterate through the array and at each iteration update the segment tree by adding 1 to the initial position of the element.
In rt[i] keep the root of the segment tree after updating all the elements for which lst[i] <= i.
Now at each query the answer will be the sum on interval l..r from the segment tree with the root rt[l — 1].
Note that after each update operation on the persistent segment tree, log n nodes will change,therefore the memory complexity is O(n log n)