Persistent Segment trees (number of distinct elements in a subarray)

Revision en1, by force_awakens, 2017-06-15 17:45:59

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?

Tags persistent segment tree, d-query

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English force_awakens 2017-06-15 17:45:59 477 Initial revision (published)