sicho_mohit's blog

By sicho_mohit, history, 2 months 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

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it
Spoiler
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh pardon me , I was not aware of that thing. I have updated the links.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

online distinct elements queries need persistent segtree i think

»
2 months 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).

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sicho_mohit (previous revision, new revision, compare).

»
2 months 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.

»
2 months 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.

»
2 months 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.

  • »
    »
    2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for advice.Will do so.