Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### force_awakens's blog

By force_awakens, history, 3 years ago, ,

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?

• +4

 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   0 Thanks got it :D
 » 3 years ago, # | ← Rev. 2 →   +1 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)
•  » » 3 years ago, # ^ |   0 Thanks got it :D