mohit_joshi's blog

Need hints in few Segment Tree problems.
By mohit_joshi, history, 3 years ago, In English

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
Thanks a lot in advance.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it
Spoiler
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

online distinct elements queries need persistent segtree i think

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

  1. Your code is invisible for us. We can't see your submission on spoj.

  2. 1st and 2nd problems where discussed on codeforces — search it (1st using bit or segtree here).

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 6   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

I suggest this article.

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Why are you solving problems involving segment trees? Go solve some constructive/math/implementation 1200, not this garbage.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    should have quoted

    Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

    → Reply