### mohit_joshi's blog

By mohit_joshi, history, 18 months ago, 1.DQUERY I know , it can be done using Mo's algorithm , but I need some hints to solve this using segment tree only. I even tried but It gave WA. Mycode
2.ANDROUND — AND Rounds
3.NICEDAY I tried this but again it gave me WA. But I think , my approach was wrong. My code  Comments (9)
| Write comment?
 » SpoilerSPOJ submissions are not public:)
 » online distinct elements queries need persistent segtree i think
 » 18 months ago, # | ← Rev. 3 →   Your code is invisible for us. We can't see your submission on spoj. 1st and 2nd problems where discussed on codeforces — search it (1st using bit or segtree here).
•  » » 18 months ago, # ^ | ← Rev. 2 →   Thanks. I actually read that blog before posting. this comment I tried to implement that but i was not getting one thing , if we are calculating sum for each r, then do we need to build the segment tree again and again? How will our build function be like? By the way ,I read this article from the link. Article Will try to implement it.Thanks.
•  » » » 18 months ago, # ^ | ← Rev. 6 →   He is actualy going trough array(1->n) and keeps 1's on last occurrences of every number and 0's on all previous occurrences of same. Then he just takes a sum(l, r) on a segtee. That is one smart trick. So no — he is not rebuilding a segtree, but yes — he has a (n,0) segtree on start and then change 0-> and 1->0 (max 2 times for every number in array).PS. But I would really like to get your attention on this comment — it doesn't seem that your problem now is in segtrees. It seems you really need to train speed-solving simple problems. I actually started at leetcode — it has a steeper learning curve.
 » Hello, I once created tutorial of sweep line or mainly sweep concept in general, in that I have explained dquery, kquery spoj, hope you will like it. I have used Fenwick tree for range addition point update, but you can also use segment tree for the same. https://youtu.be/_McXnKpGLhg If you like the video share it with your friends.
»
18 months ago, # |
Rev. 2

### Solution for the first problem

Let's consider the array is $a_1, a_2, \dots, a_n$.

For each position $i$, consider $prev[i]$ to be the last $j < i$ such that $a_j = a_i$, (or $0$ if such $j$ does not exist). Then, for a range, you can count each distinct element the first time it appears on that range; therefore, the number of distinct elements in a range $[l, r]$ is equal to the number of $i\in[l, r]$ such that $prev[i] < l$.

Now, the problem becomes, given an array (in this cases is $prev[\ ]$), and given some queries consisting of a range $[l, r]$ and a number $x$, count the number of elements in the array that are less than $x$. For sure this problem is easier. You can have a segment tree, and keep on each node of the segment tree a sorted vector with all the elements belonging to the range that node represents. This Segment Tree can be constructed easily in $\mathcal{O}(n\cdot \log n)$ time, and it consumes $\mathcal{O}(n\cdot \log n)$ space, because each element of the array has a copy in its $\mathcal{O}(\log n)$ parents. Then, for answering a query, just go through the segment tree, and for each of the important nodes you can do a binary search over its sorted vector for finding how many elements $< x$ it contains. Each query's answer is computed in $\mathcal{O}(\log^2 n)$, although you can do it in $\mathcal{O}(\log n)$ with a technique called Fractional Cascading. You could have also used a Persistent Segment Tree. Be aware that this is an online solution, you could have easier solutions if you preprocess all the queries; indeed, the Persistent Segment Tree approach is the same as the offline approach but memorizing the state of each position to make it online.