### rishichowdhury711's blog

By rishichowdhury711, history, 5 weeks ago,

Hello codeforces , I have a problem which I am unable to solve.The Problem is that you are given an array of length n (1 <= n <= 1e5) . Also you are given q (1 <= q <= 1e5) queries of form (l,r) where (1 <= l <= r <= n) . For each query you have to find the sum of distinct elements in the subarray [l,r].

For example :

if arr[]={1,2,3,4,4} and q=2, and the queries are:

1 3

2 5

so for the above queries the answer would be :

6

9

I am unable to solve this question. Any help regarding this would be helpful .Thank you

 » 5 weeks ago, # |   +13 You can solve it offline. First sort the queries by increasing order of $r$. Then maintain an array or map (depends on the values range of $a_i$) named as $previousOccurence$, such that $previousOccurence[i]=j\textrm{, such that, }j •  » » 5 weeks ago, # ^ | 0 Thanks  » 5 weeks ago, # | 0 I am wondering if we can use Mo's here? transition from f(l, r) to f(l, r + 1) or f(l, r — 1) is log(n) if set is used but the overall time complexity is O(n*sqrt(n)*log(n)) which I think could be too much •  » » 5 weeks ago, # ^ | ← Rev. 2 → 0 Mo's can be optimized to$O(Q\sqrt N)$using discretization + SQRT Decomposition. •  » » » 5 weeks ago, # ^ | 0 What is discretization? •  » » » » 5 weeks ago, # ^ | -20 There is this new invention that data scientists have been working on for decades, and it's finally made available to the public. It's called Google. You can access it by clicking this. When you're at the search page, type in "discretization" and click the first link that appears, which is most likely this. Then, please go read the article. •  » » » » » 5 weeks ago, # ^ | 0 Could have explained quicker what it actually is but had to spend efforts on award winning sarcasm ofcourse. This dude is fun  » 5 weeks ago, # | ← Rev. 2 → 0 (Edited because I misread the question)Discretize (remember to keep track of the original values because we want to find sum) and use Mo's algorithm. The transitions are$O(1)$so the total time complexity is$O(Q\log Q+Q\sqrt N)$, or amortized$O(\sqrt N)\$.
 » 5 weeks ago, # |   0 You could make root n buckets of length root n and keep a frequency map for each.Then just merge according the map according to your requirements from l to r, so it will be worst case(root n (left excess) + root n (whole blocks) + root n (right excess) ) * (map size) per queryThe problem here is that map size can be the number of distinct elements in our array in worst case, do you have a constraint on a[i]?If you're given all the queries at the start then you can even do a sweep line and difference array type thing, i think.