Code_sprinter's blog

Number of distinct elements in a subarray(solving online)
By Code_sprinter, history, 5 years ago, In English

hello everyone,

Recently i came across this problem http://www.spoj.com/problems/DQUERY/en/. I solved the problem using Mo's algo and BST which is basically offline solution. Is there a way I can solve for each query online (and similarly for trees that involves queries on the subtree of its nodes)? If yes, please help me out.

Thanks in advance!!

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

You can use merge Sort Tree to solve this problems. Here you can see sample code of merger sort tree

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

You could use a BIT (segment or fenwick tree) of size 1e6 and update the positions of the a[i] setting that to 1. Then query the range will tell the number of distinct elements.

Edit: But more simple would be to use prefix sums on an array of size 1e6.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I didn't get how you gonna solve query with that.

    Can you please elaborate a bit on how to get answer for any given l and r using segment or fenwick tree?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Well, a simple BIT returns the sum of elements in the query range. Since the values of a[] are limited to 1e6, we use a BIT of size 1e6.

      Then set the values in the BIT at positions of all a[i] to 1. Note that if two a[i] are same, we maybe twice set the value at position a[i] to 1. We could implement this update as query of that position, and only update if it is 0.

      Then the query of a range l,r will return the sum of the numbers in that range. Since the sum of the ones equals the number of the ones, it is the number of distinct elements.

      But as written, doing the same on a prefix sum array would be simpler. I was irritated by the meaning of offline.

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

What an interesting coincidence!! Codechef has a very similar problem : https://www.codechef.com/JUNE20A/problems/DIFVAL

Please wait a few days more for contest to get over and you can read the editorial.

Feel free to research on your own till then, but please refrain asking someone about it since other contestants might get solution without working for it.

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

You can use persistent data structures like persistent segment tree

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Yes! You can use Persistent Segment Tree for online answering to queries.

    You need to keep roots of versions and last positions for each value.

    1. Preprocessing:

        For each position i:
      - if we meet a[i] for first time, add 1 to position i
      - else add -1 to position of last a[i] and add 1 to current position

    2. Answering to queries

        Query: Left, Right

    We take sum from position Left to Right from version of Right position. Sum of ones in this segment will an answer for current query.
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Exactly

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

      Could u elaborate again, I could not understand the above explanation.

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

        Alright. Firstly, you need to know using Persistent Segment Tree (update, etc.). Secondly, you need to keep only roots of updated versions in versions array. Thirdly, as I said above you should put 1 only in last seen position of current value (it means, keep positions in array last and do 0-1 update on positions). Fourthly, because of updating last position in r, we take answer from version[r] between l and r.

        Also, you may see my solution for better understanding.

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

          thanks, that means each query can be answered in logn time online which is better than using merge sort tree where it takes (logn)^2 for each query.

          → Reply